22903번 - 오렌지 농장 시뮬레이션 서브태스크

브루는 오렌지 농장 시뮬레이션 게임을 하고 있다. 브루는 오랜 시간 동안 게임을 진행하며 농장에 $N$개의 오렌지 밭을 만들었으며, 이들을 $N-1$개의 도로를 통해 서로 오갈 수 있도록 연결하였다.

농장의 규모가 커지자 브루는 적당한 도로 하나를 끊어 농장을 둘로 나누려고 한다. 농장을 둘로 나누면 양쪽 농장이 동시에 성장하기 때문에 효율이 높아진다. 하지만 농장을 둘로 나눌 경우 양쪽 농장은 경쟁 관계에 들어선다. $i$번 밭의 경쟁력은 $A_i$인데, $i$번 밭과 $j$번 밭이 서로 경쟁 관계일 경우 두 밭 간의 경쟁 지수는 $A_i \oplus A_j$가 된다. (단, $\oplus$는 비트 XOR을 의미한다.) 도로 하나를 끊었을 때의 총 경쟁 지수는, 도로를 끊었을 때 발생하는 모든 경쟁 관계의 경쟁 지수의 최댓값으로 정의한다.

예를 들어, 위 예시 그림의 농장에서 $A_i = i$이고, 2번 농장과 3번 농장을 끊어 아래 그림과 같이 되었을 경우를 생각해 보자.

이때 발생하는 모든 경쟁 관계의 경쟁 지수를 구하면 아래와 같다.

• 3번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 2, 1, 7, 4
• 5번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 4, 7, 1, 2
• 6번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 7, 4, 2, 1

이들 중 최댓값은 7이다. 따라서 2번 밭과 3번 밭 사이의 도로를 끊었을 때의 총 경쟁 지수는 7이 된다.

당신은 각 도로를 끊었을 때의 총 경쟁 지수를 모두 계산하는 프로그램을 작성해야 한다.

첫 줄에는 오렌지 밭의 수 $N$이 주어진다.

둘째 줄에는 각 밭의 경쟁력 $A_1, A_2, \cdots, A_N$이 주어진다.

셋째 줄부터 $N+1$번 줄까지, $i+2$번 줄에는 $i$번 도로가 잇는 두 밭의 번호가 $u_i \ v_i$의 형태로 주어진다.

각 도로를 끊었을 때의 총 경쟁 지수를 1번 도로부터 $N-1$번 도로까지 차례로 한 줄에 하나씩 출력한다.

• $2 \le N \le 2 \times 10^5$
• $0 \le A_i < 2^{20}$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• 입력으로 주어지는 도로를 통해 모든 밭 사이를 오갈 수 있다.