点分树 | 直面恐惧，创造未来

可以说是带修改的点分治。（当然也可以不带修改，是那种需要多次询问的）

灵活性很强，我们可以维护一些树上点对问题。

话不多说了，直接进入正题。

具体操作

我们考虑对于保存点分治的路径,然后把这些点依次连接起来，点分树就建好啦。（很显然这个只是把树重构，然后保证树高为 $log\ n$）

可以发现这样的搞法可以把一些邪教的暴力变得没那么邪教。

但是单走暴力显然是不优的，我们同样是维护当前点关于其子树的信息，一般考虑使用动态开点的数据结构（比如 vector树状数组动态开点线段树）

修改和查询都可以考虑不断的从修改或查询点跳父亲，按照情况修改即可。

题目细讲

上模板题震波

翻译一下题意，就是说给你一棵树，每个点有价值，支持修改和查询操作。每次修改可以修改一个点的价值。然后查询需要求出到当前点距离小于等于 $k$ 的点的价值和。

我们可以考虑对于每个点分树上的点维护两个子树信息，一个是自己子树内的到自己的距离为 $x$ 的点的权值和，一个是自己子树内节点对点分树内的父亲的贡献的权值和，就可以方便容斥进行啦。查询的时候查询父亲点的子树内贡献与当前点子树内对父亲节点的答案的贡献的差即可。查询范围是 $k-dis$ ，其中 $dis$ 是查询点到当前点的距离。需要注意的是我们需要一直跳父亲，跳到点分树根为止。

Code:(用到了ST表求LCA ST表求LCA)

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define ReadOnly(a) freopen(#a".in","r",stdin)
#define LL long long
#define N 100000+3
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
inline int Max(int x,int y){
	return x>y?x:y;
}
inline void Swap(int &x,int &y){
	int tmp=x;x=y;y=tmp;
}
inline int Min(int x,int y){
	return x<y?x:y;
}
vector<int>head,to,nxt;
void join(int u,int v){
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
}
int n,Q;
int p[N];
int STdep[N<<1],STapp[N<<1],STdfn[N];
int dep[N];
int idx;
void dfs1(int u,int f,int deep){
	dep[u]=deep;
	STdfn[u]=++idx;
	STapp[idx]=u;
	STdep[idx]=deep;
	for(int i=head[u];~i;i=nxt[i]){
		if(to[i]==f) continue;
		dfs1(to[i],u,deep+1);
		STdep[++idx]=deep;
		STapp[idx]=u;	
	}
}
int lg2[N<<1],st[N<<1][20+3];
inline void init_ST(){
	int nn=n<<1;
	for(int i=1;i<=nn;++i){
		st[i][0]=i;
	}
	lg2[1]=0;lg2[2]=1;
	for(int i=3;i<=nn;++i){
		lg2[i]=lg2[i>>1]+1;
	}
	for(int j=1;(1<<j)<=nn;++j){
		for(int i=1;i+(1<<j)-1<=nn;++i){
			int a=st[i][j-1],b=st[i+(1<<(j-1))][j-1];
			if(STdep[a]<STdep[b]) st[i][j]=a;
			else st[i][j]=b;
		}
	}
}
inline int LCA(int x,int y){
	int l=STdfn[x],r=STdfn[y];
	if(l>r) Swap(l,r);
	int k=lg2[r-l+1];
	int a=st[l][k],b=st[r-(1<<k)+1][k];
	return STdep[a]<STdep[b]?STapp[a]:STapp[b];
}
inline int dist(int x,int y){
	return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);
}
int rt,weight[N],sz[N];
int SZ;
bool vis[N];
void GetRoot(int u,int f){
	sz[u]=1;weight[u]=-1;
	for(int i=head[u];~i;i=nxt[i]){
		if(to[i]==f||vis[to[i]]) continue;
		GetRoot(to[i],u);
		sz[u]+=sz[to[i]];
		weight[u]=Max(weight[u],sz[to[i]]);
	}
	weight[u]=Max(weight[u],SZ-sz[u]);
	if(!rt||weight[u]<weight[rt]){
		rt=u;
	}
}
int fa[N];
vector<int>C[2][N];
int tot;
void dfs(int u){
	vis[u]=1;
	sz[u]=SZ+1;
	C[0][u].resize(sz[u]+3);
	C[1][u].resize(sz[u]+3);
	for(int i=head[u];~i;i=nxt[i]){
		if(vis[to[i]]) continue;
		SZ=sz[to[i]];rt=0;GetRoot(to[i],u);
		fa[rt]=u;
		dfs(rt);
	}
}
inline void add(int cur,int kind,int x,int k){
	++x;
	for(;x<=sz[cur];x+=(x&-x)) 
		C[kind][cur][x]+=k;
}
inline int find(int cur,int kind,int y){
	++y;int res=0;
	y=Min(y,sz[cur]);
	for(;y;y-=(y&-y))
		res+=C[kind][cur][y];
	return res;
}
inline void modify(int x,int k){
	for(int i=x;i;i=fa[i]) add(i,0,dist(x,i),k);
	for(int i=x;fa[i];i=fa[i]) add(i,1,dist(x,fa[i]),k);
}
int last=0,ans=0;
int main(){
	//file(a);
	//ReadOnly(a);
	n=read();Q=read();
	head.resize(n+3,-1);
	for(int i=1;i<=n;++i){
		p[i]=read();
	}
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		join(u,v);join(v,u);
	}
	dfs1(1,1,1);
	init_ST();
	SZ=n;rt=0;GetRoot(1,1);
	dfs(rt);
	for(int i=1;i<=n;++i) modify(i,p[i]);
	while(Q--){
		int opt=read(),x=read()^last,k=read()^last;
		if(opt==1){
			modify(x,k-p[x]);
			p[x]=k;
		}else{
			ans=0;
			ans+=find(x,0,k);
			for(int i=x;fa[i];i=fa[i]){
				int dis=dist(x,fa[i]);
				if(k>=dis) ans+=find(fa[i],0,k-dis)-find(i,1,k-dis);
			}
			printf("%d\n",ans);
			last=ans;
		}
	}
	return 0;
}