9610 - 异或

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 3 秒

内存限制 : 256 MB

现在有一颗以 $1$ 为根节点的由 $n$ 个节点组成的树，节点从 $1$ 至 $n$ 编号。树上每个节点上都有一个权值 $v_i$ 。现在有 $q$ 次操作，操作如下：

输入的第一行是两个整数，分别代表结点个数 $n$ 和询问个数 $q$ 。

第二行有 $n$ 个整数，第 $i$ 个整数表示点 $i$ 的的权值 $v_i$ 。

接下来 $n-1$ 行，每行有两个整数 $u, v$ ，表示存在一条连结 $u$ 和 $v$ 的边。

接下来 $q$ 行，每行首先有一个整数 $op$ ，代表操作类型。

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

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

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

对于 $10\%$ 的数据，保证 $n, q \leq 10^2$ ；
对于 $20\%$ 的数据，保证 $n, q \leq 10^3$ ；
对于 $40\%$ 的数据，保证 $n, q \leq 10^4$ ；
对于 $100\%$ 的数据，保证 $2\leq n, q \leq10^5$ ， $1 \leq u, v, x, y \leq n$ ， $1 \leq op \leq 2$ ， $1 \leq v_i, z \lt 2^{30}$ 。

天津省选