Alice and Bob are playing the game "Cut The Tree"on a tree T with n nodes indexed from 1 to n.
For each node u , there is a mysterious weights wu on it.
The game will be played in the following order:
1. Alice choose an edge of the tree and cut it. So the tree T will be divided into two new trees T1, T2 .
2. Bob selects one of the two trees to take away, and gives the other to Alice.
3. Bob selects two nodes u, v from his tree ( u = v is allowed), and his score is wu ⊕ wv , where ⊕ means
bitwise XOR. And so for Alice, she selects two nodes u
0
, v0
from her own tree ( u
0 = v
0
is allowed), and
her score is wu0 ⊕ wv
0 .
The final score of the game is Bob’s score minus Alice’s score. Bob wants to maximize it, while Alice
wants to minimize it.
If both of them is clever enough, what’s the final score of the game?
输入格式
The first line of the input contains an integer T (1 ≤ T ≤ 5), indicating the number of the test cases.
For each test case:
The first line contains a single integer n (2 ≤ n ≤ 2×105
), indicating the number of the nodes of the tree.
The second line contains n integers w1, w2 . . . , wn (0 ≤ wi ≤ 109
), indicating the weight of the nodes.
Then the following n − 1 lines, each line contains two integers ui
, vi (1 ≤ ui
, vi ≤ n, ui 6= vi) , indicating
an undirected edge of the tree.
It’s guaranteed that the graph is a tree.
输出格式
For each test case, print one line contains a single integer, indicating the final score of the game.