트리와 XOR

정점이 $n$개인 트리가 주어진다. 각 정점에는 $1$부터 $n$까지의 번호가 붙어 있고, $i$번 정점에는 정수 $a_{i}$가 쓰여 있다. 당신은 원하는 만큼 시행을 하여 모든 $a_{i}$를 같게 만들어야 한다.

한 번의 시행에서 당신은 정점 $v$와 음이 아닌 정수 $c$를 선택한다. 그 다음 $v$를 루트로 하는 서브트리의 모든 정점 $i$에 대하여, $a_{i}$를 $a_{i}$를 $a_{i} \oplus c$로 바꾼다. $v$를 루트로 하는 서브트리의 크기를 $s$라 할 때, 이 시행의 비용은 $s \cdot c$이다. $\oplus$는 bitwise XOR을 의미한다.

$r$번 정점이 트리의 루트일 때 목표를 달성하기 위한 최소 비용을 $m_{r}$이라 하자. $m_{1}, m_{2}, \ldots, m_{n}$을 구하여라.

각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 10^{4}$). 다음 줄부터 각각의 테스트 케이스가 주어진다.

각각의 테스트 케이스의 첫 번째 줄에 정수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^{5}$).

두 번째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$가 주어진다 ($0 \le a_i < 2^{20}$).

다음 $n-1$개의 줄에 트리의 간선이 잇는 정점의 번호를 나타내는 두 정수 $u$와 $v$가 공백으로 구분되어 주어진다 ($1 \le u, v \le n$),

주어진 간선이 트리를 이룸이 보장된다.

모든 테스트 케이스에서 $n$의 총합은 $2 \cdot 10^{5}$를 넘지 않는다.

각각의 테스트 케이스마다 $n$개의 정수 $m_1, m_2, \ldots, m_n$을 공백으로 구분하여 출력한다.

첫 번째 테스트 케이스에서, 다음 방법으로 목표를 달성할 수 있다.

1. 첫 번째 시행에서 $v=2$, $c=1$을 선택한다. 시행 후 $a=[3, 3, 0, 1]$이 된다. 이 시행의 비용은 $3$이다.
2. 두 번째 시행에서 $v=3$, $c=3$을 선택한다. 시행 후 $a=[3, 3, 3, 1]$이 된다. 이 시행의 비용은 $3$이다.
3. 세 번째 시행에서 $v=4$, $c=2$를 선택한다. 시행 후 $a=[3, 3, 3, 3]$이 된다. 이 시행의 비용은 $2$이다.

이 과정의 총 비용은 $3+3+2=8$이다. $8$ 미만의 비용으로 목표를 달성하는 방법이 없음을 증명할 수 있다.

$m_{2}$, $m_{3}$, $m_{4}$도 마찬가지로 찾을 수 있다.

두 번째 테스트 케이스에서, 정점이 하나이므로 목표가 이미 달성되었다.