tree

Time Limit
8s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/1)
Description:

Given a rooted tree(node 1 is the root) with n nodes. The ithnode has a positive value vi at beginning.
We define the universal set S includes all nodes.
There are two types of Memphis's operation.
First, Memphis may change the value of one node. It's the first type operation:

0  u  v   (u∈S,0≤v≤109)

What's more, Memphis wants to know what's the maxinum of vu⊗vt(t∈path(u,root),⊗  means  xor) . It's the second type operation:
1  u   (u∈S)

Input:

This problem has multi test cases(no more than 3). 
The first line contains a single integer T, which denotes the number of test cases.
For each test case,the first line contains two non-negative integer n,m(1≤n,m≤100000) - the number of nodes and operations.
The second line contains n−1 non-negative integer f2∼fn(fi<i) - the father of ithnode.
The third line contains n non-negative integer v1∼vn(0≤vi≤109) - the value of nodes at beginning.
Follow m lines describe each operation.

Output:

For each test cases,for each second operation print a non-negative integer.

Sample Input:
1
10 10
1 1 2 2 3 1 2 3 5
23512 460943 835901 491571 399045 97756 413210 800843 283274 106134
0 7 369164
0 7 296167
0 6 488033
0 7 187367
0 9 734984
1 6
0 5 329287
1 5
0 7 798656
1 10
Sample Output:
766812
351647
431641
Source:

2015 Multi-University Training Contest 8


Submit