#361. 【模板】[动态点分治][点分树]震波

【模板】[动态点分治][点分树]震波

【模板】点分树 | 震波

题目背景

模板题,没有 raprap

题目描述

在一片土地上有 nn 个城市,通过 n1n-1 条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为 11,其中第 ii 个城市的价值为 valueivalue_i

不幸的是,这片土地常常发生地震,并且随着时代的发展,城市的价值也往往会发生变动。

接下来你需要在线处理 mm 次操作:

0 x k 表示发生了一次地震,震中城市为 xx,影响范围为 kk,所有与 xx 距离不超过 kk 的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和。

1 x y 表示第 xx 个城市的价值变成了 yy

为了体现程序的在线性,操作中的 xxyykk 都需要异或你程序上一次的输出来解密,如果之前没有输出,则默认上一次的输出为 00

输入格式

第一行包含两个正整数 nnmm

第二行包含 nn 个正整数,第 ii 个数表示 valueivalue_i

接下来 n1n-1 行,每行包含两个正整数 uuvv,表示 uuvv 之间有一条无向边。

接下来 mm 行,每行包含三个数,表示 mm 次操作。

输出格式

包含若干行,对于每个询问输出一行一个正整数表示答案。

样例 #1

样例输入 #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%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。