#2577. 「TJOI2018」xor

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

现在有一颗以 1 为根节点的由 n 个节点组成的树,树上每个节点上都有一个权值 v_i 。现在有 Q 次操作,操作如下:

  • 1 x y :查询节点 x 的子树中与 y 异或结果的最大值。
  • 2 x y z :查询路径 x y 上点与 z 异或结果最大值

输入格式

第一行是两个数字 n , Q
第二行是 n 个数字用空格隔开,第 i 个数字 v_i 表示点 i 上的权值。
接下来 n-1 行,每行两个数, x,y ,表示节点 x y 之间有边。
接下来 Q 行,每一行为一个查询,格式如上所述。

输出格式

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

样例

样例输入

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

样例输出

7
6
12
11
14

数据范围与提示

对于 10\% 的数据,有 1 \le n, Q \leq 100
对于 20\% 的数据,有 1 \le n, Q \leq 1000
对于 40\% 的数据,有 1 \le n, Q \leq 10000
对于 100\% 的数据,有 1 \le n, Q \leq 100000 ,查询 1 中的 y \leq 2^{30} ,查询 2 中的 z \leq 2^{30}