测评记录 戳我，在 tlq 没有找到相同病因，故发贴求助各位 dalao（跪

下载数据后发现问题在于第一个询问就错了，导致后面解密出问题。但是不知道第一个询问怎么错的，可数据太大了我调不了（

参考的是目前的第一篇题解，使用双线段树，动态开点，超详细注释见下。

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
int n, q, v[MAXN], lastans;// 点数, 询问, 点值, 解密用的 lastans
vector<int> g[MAXN];// 树的样子, 邻接表

namespace DFZ {

	const int INF = 0x3f3f3f3f;
	bitset<MAXN> cat;// cat = cut, build 过程记录结点是否被切除中用到的
	int dfzfa[MAXN];// dfz-father, 每个点在淀粉熟上的父亲
	int bfa[MAXN];// block-father, 每个点分治连通块内的根
	int siz[MAXN];// 视情况使用, 经常复用(
	int mySGT[MAXN];// 以自己为根开始搜索, 记录的线段树
	int rtSGT[MAXN];// 以 bfa 为根开始搜索, 记录的线段树

	pair<int, int> CoG(int u, int alsiz, int fa = -1) {
		// 找重心, CoG-Center of Gravity(?)
		// 返回值指 {siz, node}, 最大连通块大小-其重心
		// alsiz 用来 (alsiz - siz[u]) 计算用
		siz[u] = 1;
		int me = 0;// 以自己为重心所得最大连通块大小
		pair<int, int> res(INF, 0);// 返回值
		for (int v : g[u]) {
			if (v == fa || cat[v])
				continue;
			pair<int, int> t = CoG(v, alsiz, u);
			siz[u] += siz[v];
			res = min(res, t);
			me = max(me, siz[v]);
		}
		return min(res, {max(me, alsiz - siz[u]), u});
	}

	namespace SGT {

		const int MAXMEM = MAXN * 100;
		int nl[MAXMEM], nr[MAXMEM];// 结点下标左右边界
		int sum[MAXMEM], ls[MAXMEM], rs[MAXMEM];// 和值, 左右儿子
		int cnt = 1;// 动态开点内存分配的指针, 0 要空出来当空结点

		int newnode(int l, int r) {
			// 分配下标在 [l, r] 的新结点
			return nl[cnt] = l, nr[cnt] = r, cnt ++;
		}

		int query(int l, int r, int x) {
			// 查询 [l, r] 的和
			if (x == 0 || r < nl[x] || nr[x] < l)
				return 0;
			if (l <= nl[x] && nr[x] <= r)
				return sum[x];
			return query(l, r, ls[x]) + query(l, r, rs[x]);
		}

		void add(int i, int v, int x) {
			// 下标为 [i] 的数值 += v
			if (i < nl[x] || nr[x] < i)
				return;
			sum[x] += v;
			if (i == nl[x] && nr[x] == i)
				return;
			int mid = (nl[x] + nr[x]) >> 1;
			add(i, v, ls[x] ? ls[x] : ls[x] = newnode(nl[x], mid));// 如果接下来有空结点
			add(i, v, rs[x] ? rs[x] : rs[x] = newnode(mid + 1, nr[x]));// 就要分配下去
		}

	}

	void getRTSGT(int u, int addto, int dis = 0, int fa = -1) {
		// 获得 addto 的 rtSGT
		SGT :: add(dis, v[u], rtSGT[addto]);
		for (int v : g[u])
			if (v != fa && !cat[v])
				getRTSGT(v, addto, dis + 1, u);
	}

	void getMYSGT(int u, int addto, int dis = 0, int fa = -1) {
		// 获得 addto 的 mySGT, 顺便计算 siz[]
		SGT :: add(dis, v[u], mySGT[addto]);
		siz[u] = 1;
		for (int v : g[u]) {
			if (v == fa || cat[v])
				continue;
			getMYSGT(v, addto, dis + 1, u);
			siz[u] += siz[v];
		}
	}

	namespace RMQLCA {

		int fa[MAXN], dfn[MAXN], dep[MAXN];// 原树父亲, dfs 序, 深度
		int st[20][MAXN], tick;// st 表, 分配 dfs 序用的计数器

		int mdn(int u, int v) {
			// min-depth-node, 返回两结点中更浅的结点
			return dep[u] < dep[v] ? u : v;
		}

		void build(int u = 1) {
			// 预处理 st 表, 这里是搜索和 st 表二合一
			// 先搜索...
			st[0][dfn[u] = ++ tick] = u;
			for (int v : g[u]) {
				if (v == fa[u])
					continue;
				fa[v] = u, dep[v] = dep[u] + 1;
				build(v);
			}
			// 再处理 st 表...
			if (u == 1)
				for (int i = n; i >= 1; i --)// 从后往前!!!
					for (int v = 1; i + (1 << v) - 1 <= n; v ++)
						st[v][i] = mdn(st[v - 1][i], st[v - 1][i + (1 << (v - 1))]);
		}

		#define log2 __builtin_log2

		int LCA(int u, int v) {
			// 求两点 LCA
			if (u == v)
				return u;
			u = dfn[u], v = dfn[v];
			if (u > v) swap(u, v);
			u ++;
			int p = log2(v - u + 1);
			return fa[mdn(st[p][u], st[p][v - (1 << p) + 1])];
		}

		int dis(int u, int v) {
			// 求两点距离
			return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);
		}

	}

	void build(int rt = 1, int fa = -1, int bsiz = n) {
		// 构造淀粉熟, 递归下来时, 该连通块的根 rt, 上一层的重心 fa, 块的大小 bsiz
		// RMQLCA 初始化部分, 又是两部分二合一...
		if (rt == 1)
			RMQLCA :: build();
		// 下面是正常的 build
		int u = CoG(rt, bsiz).second;// 找重心 u
		bfa[u] = rt;// u 在块内的父亲 rt
		dfzfa[u] = fa;// u 在淀粉熟上的父亲 fa
		rtSGT[u] = SGT :: newnode(0, bsiz - 1);// 下标只要分配到 [0, bsiz - 1] 就好了
		getRTSGT(rt, u);// 从 rt 开始搜
		mySGT[u] = SGT :: newnode(0, bsiz - 1);// 才能保证空间复杂度 O(nlgn)
		getMYSGT(u, u);// 从 u 开始搜, 所以这里打算顺便重新计算一下 siz
		cat[u] = true;// 切掉 u
		for (int v : g[u]) {
			if (cat[v])
				continue;
			build(v, u, siz[v]);// 这里的 siz 在 getMYSGT 重新算过了, 是正确的
		}
	}

	void add(int u, int vv) {
		// opt = 1 的更改点权操作, 这里的是加点权, 一样的
		for (int v = u; v != -1; v = dfzfa[v]) {
			// 一层一层往上爬, 每一层都看看吧
			SGT :: add(RMQLCA :: dis(u, v), vv, mySGT[v]);// 更新 mySGT
			SGT :: add(RMQLCA :: dis(u, bfa[v]), vv, rtSGT[v]);// 更新 rtSGT
		}
	}

	int query(int u, int d) {
		// opt = 0 的查询操作
		int res = 0, dis;// 返回值, 以及从 v 开始应该搜索的范围
		for (int v = u, pre = -1; v != -1; ) {
			// 一层一层往上爬, 每一层都看看吧
			dis = d - RMQLCA :: dis(u, v);// u 和 v 的距离要从 d 里面扣掉
			res += SGT :: query(0, dis, mySGT[v]);// 加上贡献
			res -= SGT :: query(0, dis - 1, rtSGT[pre]);// 减去重复的
			pre = v, v = dfzfa[v];// 下一层迭代--
		}
		return res;
	}

}

void input() {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i ++)
		cin >> v[i];
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
}

int main() {
	for (input(), DFZ :: build(); q; q --) {
		int opt, a, b;
		cin >> opt >> a >> b;
		a ^= lastans, b ^= lastans;
		if (opt == 0)
			cout << (lastans = DFZ :: query(a, b)) << endl;
		else
			DFZ :: add(a, b - v[a]), v[a] = b;// 改成 b 与加上 b - v[a] 等价
	} return 0;
}