TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.9% (26/31)

Submission's AC Ratio

16.3% (76/465)

Tags

Description

還記得小向嗎?對,就是那個天龍國的天才魔法少女。
身為天龍國的魔法少女,知道怎麼駕駛魔動力捷運是一定要的,小向常常在魔法空間中的魔動力捷運系統駕駛魔動力捷運。
有天,小向又在駕駛魔動力捷運了,她決定要駕駛魔動力捷運走遍整個捷運系統。

這時候問題就來了,
我們都知道,魔動力捷運系統是一個樹狀結構的捷運系統,起點站到每個車站都只有唯一的一條路徑。
每個車站都有一個魔力驅動裝置,透過這些裝置魔動力捷運就可以輕鬆的行駛。
不過因為魔力驅動裝置會互相干擾,導致某些路段必須由小向親自使用魔力來驅動魔動力捷運,一條路徑干擾越大,小向需要使用的魔力也越多。
現在總共有N個車站(包括起點站),小向希望知道起點到任何一個車站(包括起點站)之間的干擾最大值是多少,她才能先去買一些魔法餅乾補充魔力。
一條路徑干擾的量值,可以透過將路徑上的所有魔力驅動裝置的能量值進行XOR運算而求得,也就是說我們只要將路徑上的所有魔力驅動裝置的能量值XOR起來就可以了,
而干擾的最大值就是所有的子路徑中干擾值最大的那個。(子路徑就是原本路徑的其中一段)

要是魔力透支,小向可能會失眠一整年,所以小向想要好好計算最耗費魔力的量值。
但是小向要負責開魔動力捷運,於是她將任務交給你,天龍國立天龍大學魔力電機工程所畢業的高材生,她希望妳可以在她專心開魔動力捷運的時候,
幫她計算干擾的最大值,好讓她下次多帶一點魔法餅乾。

Input Format

第一行有一個整數$T$,代表共有幾組測試資料。
每筆測試資料有$n+1$行,
第一行有一個整數$n$,代表魔動力捷運系統的車站數。
接下來一行有$n$個非0整數$a_ 1, a_ 2,...,a_ n$,其中$a_ i$代表第$i$個車站的魔力驅動裝置的量值。
接下來有$n-1$行,每行有兩個整數$u,v$,代表車站$u$可以直接行駛到車站$v$。

對於30%的測資,
$3 \leq n \leq 100$
對於100%的測資,
$1 \leq T \leq 20$
$3 \leq n \leq 10^ 5$
$1 \leq a_ i \leq 10^ 9$
$1 \leq u,v \leq n$

其中編號1為起點。

Output Format

對於每一筆測試資料,請輸出$n$行整數,第$i$行代表從起點到第$i$個點的干擾最大值。

Sample Input 1

1
5
1 0 5 4 2
1 2
2 3
3 4
4 5

Sample Output 1

1
1
5
5
6

Hints

對於範例測資的第五個點,最大的干擾是在第四個點到第五個點這段路徑,量值為$2\ XOR\ 4\ =\ 6$。

Problem Source

2015建中校隊入隊考試-複試

Subtasks

No. Testdata Range Score
1 0 30
2 1 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 262144 1
1 6000 262144 262144 2