레이팅 미적용농부 존은 \(N\)개(\(1 \leq N \leq 10^5\))의 농장을 지을 계획인데, 이 농장들은 \(N-1\)개의 도로로 연결되어 트리를 이룬다(즉, 모든 농장은 서로 도달 가능하며, 사이클이 없다). 각 농장에는 소가 한 마리씩 있으며, 그 품종은 건지(Guernsey) 또는 홀스타인(Holstein)이다.
농부 존의 친구 \(M\)명(\(1 \leq M \leq 10^5\))이 자주 그를 찾아온다. 친구 \(i\)가 방문하는 동안, 농부 존은 친구와 함께 농장 \(A_i\)에서 농장 \(B_i\)까지의 유일한 도로 경로를 따라 걷는다(\(A_i = B_i\)일 수도 있다). 또한 걷는 경로 위의 어떤 소에게서든 우유를 맛볼 수 있다. 농부 존의 친구들 대부분도 농부이기 때문에, 우유에 대한 취향이 매우 확고하다. 어떤 친구들은 건지 우유만 마시고, 나머지는 홀스타인 우유만 마신다. 농부 존의 친구는 방문 동안 자신이 선호하는 종류의 우유를 마실 수 있어야만 행복해진다.
각 친구가 방문 후 행복할지 판별하여라.
문제 제공: Spencer Compton
점수 배점
- 테스트 케이스 2-5는 \(N\le 10^3, M\le 2\cdot 10^3\)을 만족한다.
문제 제공: Spencer Compton
첫째 줄에 두 정수 \(N\)과 \(M\)이 주어진다.
둘째 줄에 길이 \(N\)의 문자열이 주어진다. 문자열의 \(i\)번째 문자는 \(i\)번째 농장의 소가 건지이면 'G', 홀스타인이면 'H'이다.
다음 \(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\)는 \(i\)번째 친구가 건지 우유를 선호하면 G, 홀스타인 우유를 선호하면 H이다.
길이 \(M\)의 이진 문자열을 출력한다. 문자열의 \(i\)번째 문자는 \(i\)번째 친구가 행복하면 '1', 아니면 '0'이어야 한다.
milkvisits.in · 출력을 쓸 파일 milkvisits.out5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H10110Here, the path from farm 1 and farm 4 involves farms 1, 2, and 4. All of these
contain Holsteins, so the first friend will be satisfied while the second one
will not.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > December > Silver