#5008. [TJOI2018] 异或

    ID: 5008 远端评测题 3000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心2018各省省选可持久化进制天津

[TJOI2018] 异或

题目描述

现在有一颗以 11 为根节点的由 nn 个节点组成的树,节点从 11nn 编号。树上每个节点上都有一个权值 viv_i。现在有 qq 次操作,操作如下:

  • 1 x z1~x~z:查询节点 xx 的子树中的节点权值与 zz 异或结果的最大值。
  • 2 x y z2~x~y~z:查询节点 xx 到节点 yy 的简单路径上的节点的权值与 zz 异或结果最大值。

输入格式

输入的第一行是两个整数,分别代表结点个数 nn 和询问个数 qq

第二行有 nn 个整数,第 ii 个整数表示点 ii 的的权值 viv_i

接下来 (n1)(n-1) 行,每行有两个整数 u,vu, v,表示存在一条连结 uuvv 的边。

接下来 qq 行,每行首先有一个整数 opop,代表操作类型。

  • op=1op = 1,则一个空格后有两个整数 x,zx, z,代表查询节点 xx 的子树中的节点权值与 zz 异或结果的最大值。
  • op=2op = 2,则一个空格后有三个整数 x,y,zx, y, z,代表查询节点 xx 到节点 yy 的简单路径上的节点的权值与 zz 异或结果最大值。

输出格式

对于每一个查询,输出一行一个整数代表答案。

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%10\% 的数据,保证 n,q102n, q \leq 10^2
  • 对于 20%20\% 的数据,保证 n,q103n, q \leq 10^3
  • 对于 40%40\% 的数据,保证 n,q104n, q \leq 10^4
  • 对于 100%100\% 的数据,保证 1<n,q1051< n, q \leq10^51u,v,x,yn1 \leq u, v, x, y \leq n1op21 \leq op \leq 21vi,z<2301 \leq v_i, z \lt 2^{30}