32985번 - 트리 부수기

문제

0ドル$번부터 $N-1$번까지 $N$개의 노드를 가진 트리가 주어진다. 두 노드 $u$와 $v$에 대하여 $c(u,v)$를 다음과 같이 정의하자.

$c(u,v)$= $u$번 노드와 연결된 모든 간선을 제거한 뒤에도 0ドル$번 노드와 $v$번 노드를 잇는 경로가 존재한다면 1ドル,ドル 그렇지 않다면 0ドル$.

$N-1$자리 이진수로 표현되는 함수 $f(x)$를 다음과 같이 정의하자. 여기서 $x$는 1ドル \leq x \leq N-1$을 만족하는 정수이다.

\[ f(x) = \left( c(x, N-1)c(x, N-2)\dots c(x, 1) \right)_{(2)} \]

예시로 주어진 아래의 트리에서 $f(3)$의 값을 구해보자.

3ドル$번 노드와 연결된 모든 간선을 제거했다고 가정해 보자. 이 경우 0ドル$번 노드에서 4ドル$번 노드로 가는 경로는 존재하지 않으므로 $c(3,4)=0$이다. 반면, 여전히 0ドル$번 노드에서 1ドル$번 노드로 가는 경로는 존재하므로 $c(3,1)=1$이다. 같은 원리로 다른 노드에 대한 값들도 구할 수 있고, 최종적으로 $f(3)={00011}_{2}$이다.

이제 다음의 값을 구해보자.

$f(1) \oplus f(2) \oplus \cdots \oplus f(N-2) \oplus f(N-1)$

$\oplus$는 bitwise XOR 연산자이다. 자세한 설명은 여기를 참고하라.

입력

첫 번째 줄에 노드의 개수 $N$이 주어진다. $(3 \leq N \leq 200,000円)$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 노드의 번호 $u,\ v$가 공백으로 구분되어 주어진다. $(0\leq u,v\leq N-1;u\neq v)$

출력

$f(1) \oplus f(2) \oplus \cdots \oplus f(N-2) \oplus f(N-1)$의 값을 $N-1$자리 이진수로 출력한다.

가장 오른쪽 비트는 $c(1, 1) \oplus c(2, 1) \oplus \dots \oplus c(N-1, 1)$이다. 출력 순서에 유의하라.

제한

힌트