F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5338. -- [TJOI2018]xor

5338: [TJOI2018]xor

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 263  Solved: 169
[Submit][Status][Discuss]

Description

现在有一颗以1为根节点的由n个节点组成的树,树上每个节点上都有一个权值vi。
现在有Q 次操作,操作如下:
1  x y    查询节点x的子树中与y异或结果的最大值
2 x y z    查询路径x到y上点与z异或结果最大值

Input

第一行是两个数字n, Q;
第二行是n个数字用空格隔开,第i个数字vi表示点i上的权值 
接下来n-1行,每行两个数,x,y,表示节点x与y之间有边 
接下来Q行,每一行为一个查询,格式如上所述.
1 < n, Q ≤ 100000 ,查询1中的y ≤ 2^30 ,查询2中的z ≤ 2^30

Output

对于每一个查询,输出一行,表示满足条件的最大值。

Sample Input

7 5
1 3 5 7 9 2 4
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5
2 4 6 3
1 5 5
2 5 7 2
1 1 9

Sample Output

7
6
12
11
14

HINT

Source

[Submit][Status][Discuss]

HOME Back