思路题解

关键观察

• 点 $u$ 的权值 $w_u$ 只依赖 $a_u$ 以及 $u$ 的直接子节点的取值集合 ${a_v\mid v\in \mathrm{child}(u)}$。 因而一次把 $a_x$ 改成 $y$ 的修改，至多影响 两个点：$x$ 自身（若 $x$ 有子）与其父亲 $p=\mathrm{fa}(x)$（因为 $w_p$ 里包含$a_p\oplus a_x$ 这一候选）。这不会继续向更高祖先传递（$w_{\mathrm{fa}(mathrm{fa}(x))}$ 不依赖 $w_p$）。

• 区间查询（类型 $2$）是“按编号”的最大值；子树查询（类型 $3$）可以用欧拉序把子树压成一段区间。因此维护两棵最大值线段树即可：

  • 一棵按编号 $1\sim n$；

题目内容

小美有一棵 $n$ 个节点(编号为 $1$ ~ $n$)、由 $n-1$ 条边构成的无向树，根节点为 $1$ 。每个节点 $i$ 有一个值 $a_i$ 。对于任意节点 $u$ ，其权值定义如下：

• 如果 $u$ 有子节点，则权值为该节点与所有子节点值的按位异或的最大值，即

• 如果 $u$ 是叶子节点，则权值为 $a_u$。

接下来小美会对这棵树进行 $m$ 次操作，每次操作从以下三种类型中选择一种执行：

• 类型 $1$ $x$ $y$： 将节点 $x$ 的值 $a_x$ 修改为 $y$ ，

• 类型 $2$ $x$ $y$ ：查询当前所有编号在区间 $[l,r]$ 内的节点的最大权值，$(1≦x≦y≦n)$ ;

• 类型 $3$ $x$ ：查询以节点 $x$ 为根的子树中所有节点的最大权值，$(1 ≦x≦n)$ 。

输入描述

第一行输入两个整数 $n,m(1≦n,m ≦3×10^5)$ ，分别表示节点数和操作次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦ 10^9)$ ，表示初始时每个节点的值。

接下来 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i(1 ≦ u_i, v_i ≦ n; u_i≠v_i)$ ，表示树上第 $i$ 条树边。

随后 $m$ 行，每行对应一次操作，格式如题目描述所示。

输出描述

对于每个查询操作(类型 $2$ 或 $3$ )，输出一行，表示查询结果(最大权值)。

样例1

输入

3 4
1 2 3
1 2
1 3
2 2 3
3 1
1 1 5
3 1

输出

3 
3 
7

样例2

输入

1 2
10
2 1 1
3 1

输出

10
10