rt，除了 #3 其他都 RE，推测是 WA 后强制在线导致的。

https://www.luogu.com.cn/record/172724351

#include<bits/stdc++.h>
using namespace std;
bool f[100005];
vector<int> e[100005];
int dep[100005];
int cnt=0;
int n,m;
int sz[100005],sz_num[100005];
int fa[100005],a[100005];
int id[100005],l[100005];
int minn[200005][18],mint[200005][18],lg[200005];
vector<int> tr[200005][2];
void add(int x,int y,int z,int v)
{
	z++;
	for(;z<tr[x][y].size();z+=(z&-z))
		tr[x][y][z]+=v;
}
int query(int x,int y,int z)
{
	z++;
	z=min(z,(int)tr[x][y].size()-1);
	int ans=0;
	for(;z;z-=(z&-z))
		ans+=tr[x][y][z];
	return ans;
}
void dfs(int pos,int fa)
{
	id[++cnt]=pos;
	l[pos]=cnt;
	dep[pos]=dep[fa]+1;
	for(int x:e[pos])
		if(x!=fa)
			dfs(x,pos),id[++cnt]=pos;
}
int lca(int u,int v)
{
	if(l[u]>l[v])
		swap(u,v);
//	cout<<u<<" "<<v<<" ";
	u=l[u],v=l[v];
	int k=lg[v-u+1];
//	cout<<u<<" "<<v<<" "<<k<<"\n";
	if(minn[u][k]<=minn[v-(1<<k)+1][k])
		return mint[u][k];
	else
		return mint[v-(1<<k)+1][k];
}
int getdis(int u,int v)
{
//	cout<<u<<" "<<v<<" "<<lca(u,v)<<"\n";
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
vector<int> v;
void dfs_centroid(int pos,int fa)
{
    v.push_back(pos);
    sz[pos]=1;
    sz_num[pos]=0;
    for(int p:e[pos])
    {
        if(p==fa||f[p])
            continue;
        dfs_centroid(p,pos);
        sz[pos]+=sz[p];
        sz_num[pos]=max(sz_num[pos],sz[p]);
    }
}
int centroid(int pos)
{
    v.clear();
    dfs_centroid(pos,0);
    for(int x:v)
        if(sz_num[x]<=v.size()/2&&sz[x]>=v.size()-v.size()/2)
            return x;
}
void solve(int pos,int lst)
{
    int mid=centroid(pos);
    tr[mid][0].resize(sz[pos]+2),tr[mid][1].resize(sz[pos]+2);
    fa[mid]=lst;
    f[mid]=1;
    for(int x:e[mid])
        if(!f[x])
            solve(x,mid);
}
void addin(int x,int y)
{
	for(int i=x;i;i=fa[i])
		add(i,0,getdis(x,i),y); 
	for(int i=x;fa[i];i=fa[i])
		add(i,1,getdis(x,fa[i]),y);	
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
//    cout<<"------"<<cnt<<"\n";
    for(int i=2;i<=cnt;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=cnt;i++)
	{
		minn[i][0]=dep[id[i]];
		mint[i][0]=id[i];
	}
	for(int j=1;j<=17;j++)
	{
		for(int i=1;i<=cnt;i++)
		{
			minn[i][j]=minn[i][j-1];
			mint[i][j]=mint[i][j-1];
			if(i+(1<<(j-1))<=cnt&&minn[i+(1<<(j-1))][j-1]<minn[i][j-1])
			{
				minn[i][j]=minn[i+(1<<(j-1))][j-1];
				mint[i][j]=mint[i+(1<<(j-1))][j-1];
			}
//			cout<<i<<" "<<j<<" "<<mint[i][j]<<"\n";
		}
	}
    solve(1,0);
//	for(int i=1;i<=n;i++)
//		cout<<fa[i]<<"\n";
    for(int i=1;i<=n;i++)
    	addin(i,a[i]);
    int lastans=0;
    for(int i=1;i<=m;i++)
    {
    	int opt,x,y;
    	cin>>opt>>x>>y;
    	x^=lastans;
    	y^=lastans;
    	if(!opt)
    	{
    		int ans=query(x,0,y);
    		for(int j=x;fa[j];j=fa[j])
    		{
    			int dis=getdis(fa[j],x);
//    			cout<<dis<<"\n";
    			if(dis>y)
    				continue;
    			ans+=query(fa[j],0,y-dis)-query(j,1,y-dis);
//    			cout<<ans<<"\n";
			}
			lastans=ans;
			cout<<ans<<"\n";
		}
		else
		{
			addin(x,-a[x]);
			a[x]=y;
			addin(x,a[x]);
		}
	}
}