【模板】点分树 | 震波
题目背景
模板题,没有 $rap$ 。
题目描述
在一片土地上有 $n$ 个城市,通过 $n-1$ 条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为 $1$,其中第 $i$ 个城市的价值为 $value_i$。
不幸的是,这片土地常常发生地震,并且随着时代的发展,城市的价值也往往会发生变动。
接下来你需要在线处理 $m$ 次操作:
`0 x k` 表示发生了一次地震,震中城市为 $x$,影响范围为 $k$,所有与 $x$ 距离不超过 $k$ 的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和。
`1 x y` 表示第 $x$ 个城市的价值变成了 $y$ 。
为了体现程序的在线性,操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密,如果之前没有输出,则默认上一次的输出为 $0$ 。
输入输出格式
输入格式
第一行包含两个正整数 $n$ 和 $m$ 。
第二行包含 $n$ 个正整数,第 $i$ 个数表示 $value_i$ 。
接下来 $n-1$ 行,每行包含两个正整数 $u$、$v$,表示 $u$ 和 $v$ 之间有一条无向边。
接下来 $m$ 行,每行包含三个数,表示 $m$ 次操作。
输出格式
包含若干行,对于每个询问输出一行一个正整数表示答案。
输入输出样例
输入样例 #1
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1
输出样例 #1
11100101
说明
#### 数据规模与约定
对于 $100 \%$ 的数据,有 $1\leq n,m\leq 10^5, 1\leq u,v,x\leq n, 1\leq value_i,y\leq 10^4,0\leq k\leq n-1$ 。
upd:样例范围与题目真实数据范围不同,以提示中给出的数据范围为准。
#### 说明
题目来源:BZOJ3730。