2126: [蓝桥杯2023初赛] 异或和

内存限制:512 MB 时间限制:3 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:92 通过:27

题目描述

给一棵含有 n 个结点的有根树,根结点为 1 ,编号为 i 的点有点权 ai(i ∈ [1, n])。
现在有两种操作,格式如下:
• 1 x y 该操作表示将点 x 的点权改为 y 。
• 2 x 该操作表示查询以结点 x 为根的子树内的所有点的点权的异或和
现有长度为 m 的操作序列,请对于每个第二类操作给出正确的结果。

输入格式

输入的第一行包含两个正整数 n, m ,用一个空格分隔。
第二行包含 n 个整数 a1, a2, ..., an ,相邻整数之间使用一个空格分隔。
接下来 n-1 行,每行包含两个正整数 ui, vi ,表示结点 ui 和 vi 之间有一条边。
接下来 m 行,每行包含一个操作。
对于 30% 的评测用例,n,m ≤ 1000;
对于 100% 的评测用例,1 ≤ n,m ≤ 100000 ,0 ≤ ai, y ≤ 100000 ,1 ≤ ui, vi, x ≤ n。

输出格式

输出若干行,每行对应一个查询操作的答案。

输入样例 复制

4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2

输出样例 复制

4
5
6