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 Av 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.
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 space-separated integers denoting Av - the values associated with nodes.
Next N-1 lines contains two space-separated integers u, v denoting the nodes connected by an edge.
For each test case for each node in range from 1 to N, output its ugliness in a single line.
- 1 ≤ T ≤ 105
- 2 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109
- 1 ≤ u, v ≤ N
- 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
Input: 1 5 1 2 3 4 5 1 2 1 3 2 4 2 5 Output: 7 7 3 4 5
|Tags||lca, ltime40, medium, mgch, optimization, tree, xor|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.