淀粉熟全T求助

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int ll
#define lowbit(x) x&(-x)
int read()
{
    ll now = 0, nev = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            nev = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        now = (now << 1) + (now << 3) + (c & 15);
        c = getchar();
    }
    return now * nev;
}
const int MAXN = 1e6 + 10;
const int mod = 998244353;
int n,m;
int a[MAXN];
int head[MAXN],tt=0;
struct edge
{
	int to,nxt,dis;
}e[MAXN<<1];
void add(int x,int y)
{
	e[++tt].nxt=head[x];
	head[x]=tt;
	e[tt].to=y;
	e[tt].dis=1;
}
int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN];
int top[MAXN];
void dfs1(int u,int fat)
{
	fa[u]=fat;
	dep[u]=dep[fat]+1;
	siz[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fat)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])
			son[u]=v;
	}
}
void dfs2(int u,int topfa)
{
	top[u]=topfa;
	if(son[u])
		dfs2(son[u],topfa);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u] || v==son[u])
			continue;
		dfs2(v,v);
	}
}
int LCA(int x,int y)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]])
            swap(x, y);
        x = fa[top[x]];
    }
    if (dep[x]>dep[y])
        swap(x, y);
    return x;
}
int dis(int x,int y)
{
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
struct BIT
{
	vector<int>bit;
	void build(int sz)
	{
		for(int i=0;i<=sz+3;i++)
			bit.push_back(0);
	}
	void add(int x,int v)
	{
		while(x<=bit.size())
		{
			bit[x]+=v;
			x+=lowbit(x);
		}
	}
	int ask(int x)
	{
		x=min(x,(int)bit.size()-1);
		int res=0;
		while(x)
		{
			res+=bit[x];
			x-=lowbit(x);
		}
		return res;
	}
}s1[MAXN],s2[MAXN];
bool vis[MAXN];
void dfs3(int rt,int u,int fat,int len)
{
	s1[rt].add(len,a[u]);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fat || vis[v])
			continue;
		dfs3(rt,v,u,len+1);
	}
}
int seg[MAXN],idx=0;
int f[MAXN];
void dfs4(int u,int fat)
{
	seg[++idx]=u;
	siz[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fat ||vis[v])
			continue;
		dfs4(v,u);
		siz[u]+=siz[v];
		f[u]=max(f[u],siz[v]);
	}
} 
void init(int u,int fat)
{
	idx=0;
	dfs4(u,0);
	for(int i=1;i<=idx;i++)
		f[seg[i]]=max(f[seg[i]],idx-siz[seg[i]]);
	int rt=-1;
	for(int i=1;i<=idx;i++)
	{
		if(rt==-1 || f[rt]>f[seg[i]])
			rt=seg[i];
	}
	for(int i=1;i<=idx;i++)
		f[seg[i]]=0;
	vis[rt]=1;
	u=rt;
	fa[u]=fat;
	s2[u].build(idx);
	if(fat)
	{
		for(int i=1;i<=idx;i++)
			s2[u].add(dis(seg[i],fat),a[seg[i]]);
	}
	s1[u].build(idx);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v])
			continue;
		dfs3(u,v,u,1);
	}
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v])
			continue;
		init(v,u);
	}
}
void modefy(int x,int v)
{
	int u=x;
	while(fa[u])
	{
		int d=dis(x,fa[u]);
		s2[u].add(d,-a[x]);
		s2[u].add(d,v);
		u=fa[u];
		s1[u].add(d,-a[x]);
		s1[u].add(d,v);
	}
	a[x]=v;
}
int query(int x,int v)
{
	int res=0;
	int u=x;
	res+=a[x]+s1[x].ask(v);
	while(fa[u])
	{
		int d=dis(x,fa[u]);
		if(d<=v)
			res+=a[fa[u]]+s1[fa[u]].ask(v-d)-s2[u].ask(v-d);
		u=fa[u];
	}
	return res;
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	dfs1(1,0),dfs2(1,0);
	init(1,0);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int op=read(),x=read(),y=read();
		x^=ans,y^=ans;
		if(op==0)
			printf("%lld\n",ans=query(x,y));
		if(op==1)
			modefy(x,y);
	}
	return 0;
}