#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e5,D=20;
int n,m,a[N],ns;
//Tree
vector<int> adj[N];
void adde(int u,int v){adj[u].pb(v),adj[v].pb(u);}
//Tree//Dis
int in,dfn[N],d[N],dv[N*2],st[D][N*2];
void maked(int u,int fa=-1){
dv[dfn[u]=in++]=d[u];
for(int v:adj[u])if(v!=fa)
d[v]=d[u]+1,maked(v,u),dv[in++]=d[u];
}
void dis_init(){
R(i,in) st[0][i]=dv[i];
R(d,D-1)R(i,in-(2<<d)+1)
st[d+1][i]=min(st[d][i],st[d][i+(1<<d)]);
}
int hcd(int u,int v){
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v); ++v;
int i=log2(v-u);
return min(st[i][u],st[i][v-(1<<i)]);
}
int dis(int u,int v){return d[u]+d[v]-hcd(u,v)*2;}
//FenwickTree
struct fenwt:vector<int>{
void add(int i,int x){for(;
i<size();i|=i+1) (*this)[i]+=x;}
int sum(int i){int x=0; for(;i>=0;
--(i&=i+1)) x+=(*this)[i]; return x;}
};
//Tree//Divide
int mx[N],sz[N],ts,g,fa[N];
fenwt s[N],f[N];
bool vis[N];
void makeg(int u,int fa=-1){
sz[u]=1,mx[u]=0;
for(int v:adj[u])if(v!=fa&&!vis[v])
makeg(v,u),sz[u]+=sz[v],mx[u]=max(mx[u],sz[v]);
mx[u]=max(mx[u],ts-sz[u]);
if(!~g||mx[u]<mx[g]) g=u;
}
vector<int> su;
void makes(int u,int fa=-1){
su.pb(u);
for(int v:adj[u])if(v!=fa&&!vis[v])
makes(v,u);
}
void divide(int u){
vis[u]=true,su.clear(),makes(u);
s[u].assign(sz(su)+1,0),f[u]=s[u];
for(int v:su) s[u].add(dis(u,v),a[v]),
~fa[u]?f[u].add(dis(fa[u],v),a[v]):void();
for(int v:adj[u])if(!vis[v])
ts=sz[v],g=-1,makeg(v),fa[g]=u,divide(g);
}
//Tree//Query
int query(int u,int k){
int res=s[u].sum(k);
for(int h=-1,v=u;~fa[v];v=fa[v])
if((h=dis(u,fa[v]))<=k)
res+=s[fa[v]].sum(k-h)-f[v].sum(k-h);
return res;
}
void modify(int u,int x){
s[u].add(0,x);
for(int h=-1,v=u;~fa[v];v=fa[v])
s[fa[v]].add(h=dis(u,fa[v]),x),f[v].add(h,x);
}
//Main
int main(){
// freopen("P6329_1.in","r",stdin);
// freopen("geo.txt","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin>>n>>m;
R(i,n) cin>>a[i];
R(i,n-1){int u,v; cin>>u>>v,adde(--u,--v);}
maked(0),dis_init();
ts=n,g=-1,makeg(0),fa[g]=-1,divide(g);
while(m--){
int o,u,x; cin>>o>>u>>x,--(u^=ns),x^=ns;
if(o) modify(u,x-a[u]),a[u]=x;
else cout<<(ns=query(u,x))<<'\n';
}
return 0;
}
有没有做过的人知道为什么总是 RE
啊,啊啊啊,啊啊啊啊啊啊啊啊啊啊啊啊啊,啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。