RiseOJ – 우유 방문

설명

농부 존은 $$N$$ 개( $1 \leq N \leq 10^5$ )의 농장을 지을 계획인데, 이 농장들은 $$N-1$$ 개의 도로로 연결되어 트리를 이룬다(즉, 모든 농장은 서로 도달 가능하며, 사이클이 없다). 각 농장에는 $$1$$ 이상 $$N$$ 이하의 정수 품종 $$T_i$$ 를 가진 소가 한 마리씩 있다.

농부 존의 친구 $$M$$ 명( $1 \leq M \leq 10^5$ )이 자주 그를 찾아온다. 친구 $$i$$ 가 방문하는 동안, 농부 존은 친구와 함께 농장 $$A_i$$ 에서 농장 $$B_i$$ 까지의 유일한 도로 경로를 따라 걷는다( $$A_i = B_i$$ 일 수도 있다). 또한 걷는 경로 위의 어떤 소에게서든 우유를 맛볼 수 있다. 농부 존의 친구들 대부분도 농부이기 때문에, 우유에 대한 취향이 매우 확고하다. 각 친구는 특정 품종의 소에게서 나온 우유만 마신다. 농부 존의 친구는 방문 동안 자신이 선호하는 종류의 우유를 마실 수 있어야만 행복해진다.

각 친구가 방문 후 행복할지 판별하여라.

문제 제공: Spencer Compton

제약

점수 배점

테스트 케이스 2는 아래의 두 번째 예제이다.
테스트 케이스 3은 $N\le 10^3, M\le 2\cdot 10^3$ 을 만족한다.
테스트 케이스 4-7은 $C_i\le 10$ 을 만족한다( $$C_i$$ 는 아래에 정의된다).

문제 제공: Spencer Compton

입력 형식

첫째 줄에 두 정수 $$N$$ 과 $$M$$ 이 주어진다.

둘째 줄에 공백으로 구분된 $$N$$ 개의 정수 $T_1,T_2,\ldots, T_N$ 이 주어진다. $$i$$ 번째 농장에 있는 소의 품종은 $$T_i$$ 로 표기한다.

다음 $$N-1$$ 개의 줄에는 각각 서로 다른 두 정수 $$X$$ 와 $$Y$$ ( $1 \leq X, Y \leq N$ )가 주어지며, 이는 농장 $$X$$ 와 $$Y$$ 사이에 간선이 있음을 나타낸다.

다음 $$M$$ 개의 줄에는 정수 $$A_i$$ , $$B_i$$ , $$C_i$$ 가 주어진다. $$A_i$$ 와 $$B_i$$ 는 친구 $$i$$ 의 방문 동안 걷는 경로의 양 끝점을 나타내고, $$C_i$$ ( $1\le C_i\le N$ )는 그 친구가 즐겨 마시는 우유를 내는 소의 품종을 나타낸다.

출력 형식

길이 $$M$$ 의 이진 문자열을 출력한다. 문자열의 $$i$$ 번째 문자는 $$i$$ 번째 친구가 행복하면 '1', 아니면 '0'이어야 한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 milkvisits.in · 출력을 쓸 파일 milkvisits.out

예제 1

입력

출력

설명

In this example, the path from 1 and 4 involves farms 1, 2, and 4. All of these
contain cows of type 1, so the first friend will be satisfied while the second
one will not.

예제 2

입력

6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Gold

올림피아드 > USACO > 2019-2020 > December > Gold

태그

JudgeUSACO

우유 방문

평가 및 의견

풀이 제출