3309. [TJOI 2018]异或

【题目描述】

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

$1~x~z$：查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。

$2~x~y~z$：查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

【输入格式】

输入的第一行是两个整数，分别代表结点个数 $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$ 异或结果最大值。

【输出格式】

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

【样例 1 输入】

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

【样例 1 输出】

7
6
12
11
14

【数据规模与约定】

对于 $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}$。