P3590.第4题-你懂的，这也是一道数学题
题目内容
小美有一棵 n 个节点(编号为 1 ~ n)、由 n−1 条边构成的无向树，根节点为 1 。每个节点 i 有一个值 ai 。对于任意节点 u ，其权值定义如下：
- 如果 u 有子节点，则权值为该节点与所有子节点值的按位异或的最大值，即
- 如果 u 是叶子节点，则权值为 au。
接下来小美会对这棵树进行 m 次操作，每次操作从以下三种类型中选择一种执行：
-
类型 1 x y： 将节点 x 的值 ax 修改为 y ，
-
类型 2 x y ：查询当前所有编号在区间 [l,r] 内的节点的最大权值，(1≦x≦y≦n) ;
-
类型 3 x ：查询以节点 x 为根的子树中所有节点的最大权值，(1≦x≦n) 。
输入描述
第一行输入两个整数 n,m(1≦n,m≦3×105) ，分别表示节点数和操作次数。
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) ，表示初始时每个节点的值。
接下来 n−1 行，第 i 行输入两个整数 ui 和 vi(1≦ui,vi≦n;ui=vi) ，表示树上第 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
