题面

大秦为你打开题目传送门

题目背景

模板题，没有 $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

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

思路

首先我们知道，单次询问，树上路径的问题可以用点分治解决。

但如果加上什么 $q$ 次询问之类的东西怎么办呢？比如说这题。

显然每次都跑一遍点分治时间复杂度肯定吃不消。

考虑把点分治的过程离线下来，将当前树的重心与上一层的树的重心连边，这样就可以得到一棵树，我们称之为“点分树”

比如说我们有如下图所示的树与基于其建立的点分树：

那么这棵树对于我们做题有什么帮助呢？

有的问题我们不是非常关心树的形态特点，比如路径问题，联通块问题，寻找关键点问题等等，以路径问题为例，我们不一定非得查到 $p,q$ 的 LCA 才可以处理 $p,q$ 的路径信息，相反，我们可以随便从这个路径上寻找一个分割点 $t$ ，只要我们可以快速的处理 $p$ 到 $t$ 和 $q$ 到 $t$ 的信息，我们就可以处理 $p$ 到 $q$ 的信息。

而点分树恰恰就是对原树做了这样的映射。