#P3730. 震波

    ID: 2943 传统题 3000ms 256MiB 尝试: 6333 已通过: 613 难度: 7 上传者: 标签>CF2300提高+/省选-点分树点分祖先维护距离树状数组点分治容斥去重动态点分治

震波

题目描述

在一片土地上有 NN 个城市,通过 N−1N-1 条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为 11,其中第 ii 个城市的价值为 value[i]value[i]。

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

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

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

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

输入格式

第一行包含两个正整数 NN 和 MM。 第二行包含 NN 个正整数,第 ii 个数表示 value[i]value[i]。 接下来 N−1N-1 行,每行包含两个正整数 uu、vv,表示 uu 和 vv 之间有一条无向边。 接下来 MM 行,每行包含三个数,表示 MM 次操作。

输出格式

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

输入样例

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

输出数据

11100101

提示

1≤N,M≤1000001 \le N,M \le 100000 1≤u,v,x≤N1 \le u,v,x \le N 1≤value[i],y≤100001 \le value[i],y\le 10000 0≤k≤N−10 \le k \le N-1