luogu P6329 【模板】点分树 | 震波

//【模板】点分树 | 震波
//https://www.luogu.com.cn/problem/P6329
#include<bits/stdc++.h>
#define debug(a) cerr<<"Line: "<<__LINE__<<" "#a<<endl
#define print(a) cerr<<#a"="<<(a)<<endl
#define sign() puts("---------")
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10;
int n,q,a[N];
struct Graph{
	int head[N],etot;
	struct node{ int nxt,v; }edge[N<<1];
	void add(int u,int v){
		edge[++etot] = {head[u],v};
		head[u] = etot;
	}
	node & operator [](const int &i){ return edge[i]; }
}G;
int st[N][20],dep[N];
void dfs(int u,int fa){
	st[u][0] = fa, dep[u] = dep[fa] + 1;
	for(int i = 1;(1<<i)<=dep[u];++i)st[u][i] = st[st[u][i-1]][i-1];
	for(int i = G.head[u];i;i = G[i].nxt)if(G[i].v != fa)dfs(G[i].v,u);
}
void scan(){
	scanf("%d%d",&n,&q);
	for(int i = 1;i<=n;++i)scanf("%d",&a[i]);
	for(int i = 1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		G.add(u,v),G.add(v,u);
	}
}
int mx[N],root,Tsiz,nwfa[N],siz[N];
bool vis[N];
void getroot(int u,int fa){
	siz[u] = 1, mx[u] = 0;
	for(int i = G.head[u];i;i = G[i].nxt){
		int v = G[i].v;
		if(v != fa && !vis[v]){
			getroot(v,u);
			siz[u] += siz[v];
			mx[u] = max(mx[u],siz[v]);
		}
	}
	mx[u] = max(mx[u],Tsiz - siz[u]);
	if(mx[u] < mx[root])root = u;
}
void solve(int u){
	vis[u] = 1;
	for(int i = G.head[u];i;i = G[i].nxt){
		int v = G[i].v;
		if(!vis[v]){
			root = 0;
			Tsiz = siz[v];
			getroot(v,u);
			nwfa[root] = u;
			solve(root);
		}
	}
}
void init(){
	mx[(root = 0)] = inf;
	Tsiz = n; getroot(1,0); solve(root);
}
int LCA(int x,int y){
	if(dep[x] > dep[y])swap(x,y);
	int t = dep[y] - dep[x];
	for(int i = 17;~i;--i)if(t & (1<<i))y = st[y][i];
	if(x == y)return x;
	for(int i = 17;~i;--i)if(st[x][i] && st[y][i] && st[x][i] != st[y][i])
		x = st[x][i], y = st[y][i];
	return st[x][0];
}
int Dis(int x,int y){ return dep[x] + dep[y] - (dep[LCA(x,y)]<<1); }
struct Segment_tree{
	int rt[N],tot;
	struct Date{ int ls,rs,val; }tr[N*50];
	void pushup(int p){ tr[p].val = tr[tr[p].ls].val + tr[tr[p].rs].val; }
	void modify(int &p,int l,int r,int x,int v){
		if(!p)p = ++tot;
		if(l == r)return tr[p].val += v,void();
		int mid = (l+r)>>1;
		if(x <= mid)modify(tr[p].ls,l,mid,x,v);
		else modify(tr[p].rs,mid+1,r,x,v);
		pushup(p);
	}
	int query(int p,int l,int r,int L,int R){
		if(!p)return 0;
		if(L <= l && r <= R)return tr[p].val;
		int mid = (l+r)>>1;
		int res = 0;
		if(L <= mid)res += query(tr[p].ls,l,mid,L,R);
		if(mid < R)res += query(tr[p].rs,mid+1,r,L,R);
		return res;
	}
}seg1,seg2;
void update(int x,int v){
	int now = x;
	while(now){
		seg1.modify(seg1.rt[now],0,n-1,Dis(now,x),v);
		if(nwfa[now])seg2.modify(seg2.rt[now],0,n-1,Dis(nwfa[now],x),v);
		now = nwfa[now];
	}
} 
int query(int x,int k){
	int now = x, pre = 0, res = 0;
	while(now){
		if(Dis(now,x) > k){
			pre = now, now = nwfa[now];
			continue;
		}
		res += seg1.query(seg1.rt[now],0,n-1,0,k-Dis(now,x));
		if(pre)res -= seg2.query(seg2.rt[pre],0,n-1,0,k-Dis(now,x));
		pre = now, now = nwfa[now];
	}
	return res;
}
int main(){
	scan();
	dfs(1,0);
	init();
	for(int i = 1;i<=n;++i)update(i,a[i]);
	int pre = 0,op,x,y;
	while(q--){
		scanf("%d%d%d",&op,&x,&y);
		x ^= pre, y ^= pre;
		if(op == 1)update(x,y-a[x]),a[x] = y;
		else{
			pre = query(x,y);
			printf("%d\n",pre);
		}
	}
	return 0;
}