Chef and Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef likes trees a lot. He has a weighted rooted tree T rooted at node 1. There are N nodes in the tree numbered from 1 to N. Each node v has a value A_{v} associated with it. Let's call ugliness of path between nodes u and v  C(u, v) as bitwise XOR of all values on path. Let's call ugliness of node v maximal ugliness among all the paths which lies in subtree v. For each node find ugliness of it.
Input
The first line contains one integer T, denoting the number of the test cases.
First line of each test case contains one integer N.
Second line contains N spaceseparated integers denoting A_{v}  the values associated with nodes.
Next N1 lines contains two spaceseparated integers u, v denoting the nodes connected by an edge.
Output
For each test case for each node in range from 1 to N, output its ugliness in a single line.
Constraints
 1 ≤ T ≤ 10^{5}
 2 ≤ N ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{9}
 1 ≤ u, v ≤ N
Subtasks
 Subtask #1 (10 points): 1 ≤ sum over all N ≤ 100
 Subtask #2 (20 points): 1 ≤ sum over all N ≤ 1000
 Subtask #3 (30 points): 1 ≤ sum over all N ≤ 10000
 Subtask #4 (40 points): 1 ≤ sum over all N ≤ 100000
Example
Input: 1 5 1 2 3 4 5 1 2 1 3 2 4 2 5 Output: 7 7 3 4 5
Author:  mgch 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/LTM40GH 
Tags  lca, ltime40, medium, mgch, optimization, tree, xor 
Date Added:  12092016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 