在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理M次操作：
0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。

第一行包含两个正整数N和M。
第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。
接下来M行，每行包含三个数，表示M次操作。

包含若干行，对于每个询问输出一行一个正整数表示答案。

1<=N,M<=100000

1<=u,v,x<=N

1<=value[i],y<=10000

0<=k<=N-1

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define N 100007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,lastans,S,tot,xj;

 int cnt,hed[N],rea[N*],nxt[N*];

 int pos[N],mn[][N*],dep[N];

 int value[N],vis[N],sz[N],fa[N],ra[N],rb[N],rt,f[N],Log[N*];

 int ls[N*],rs[N*],sum[N*],tp;

 void add(int u,int v)

 {

     nxt[++cnt]=hed[u];

     hed[u]=cnt;

     rea[cnt]=v;

 }

 void get_root(int u,int fa)

 {

     sz[u]=,f[u]=;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (vis[v]||v==fa)continue;

         get_root(v,u),sz[u]+=sz[v],f[u]=max(f[u],sz[v]);

     }

     f[u]=max(f[u],S-sz[u]);

     if (f[u]<f[rt])rt=u;

 }

 inline int dis(int x,int y)

 {

     int t=dep[x]+dep[y],k;

     x=pos[x],y=pos[y];

     if (x>y)swap(x,y);

     k=Log[y-x+];

     return t-(min(mn[k][x],mn[k][y-(<<k)+])<<);

 }

 void update(int p,int a,int l,int r,int &x)

 {

     if (!x)x=++xj;

     sum[x]+=a;

     if (l==r)return;

     int mid=(l+r)>>;

     if (p<=mid)update(p,a,l,mid,ls[x]);

     else update(p,a,mid+,r,rs[x]);

 }

 int query(int p,int l,int r,int x)

 {

     if (!x) return ;

     if (l==r) return sum[x];

     int mid=(l+r)>>;

     if (p<=mid)return query(p,l,mid,ls[x]);

     else return query(p,mid+,r,rs[x])+sum[ls[x]];

 }

 void calc(int u,int par,int p)

 {

     update(dis(u,p),value[u],,n-,ra[p]);

     if (fa[p])update(dis(u,fa[p]),value[u],,n-,rb[p]);

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (vis[v]||v==par) continue;

         calc(v,u,p);

     }

 }

 void divide(int u)

 {

     calc(u,,u),vis[u]=;int yS=S;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (vis[v])continue;

         rt=;

         if (sz[v]>sz[u])S=yS-sz[u];

         else S=sz[v];

         get_root(v,),fa[rt]=u;

         divide(rt);

     }

 }

 inline void modify(int x,int y)

 {

     for (int i=x;i!=;i=fa[i])

     {

         update(dis(x,i),y-value[x],,n-,ra[i]);

         if (fa[i])update(dis(x,fa[i]),y-value[x],,n-,rb[i]);

     }

     value[x]=y;

 }

 inline int solve(int x,int p)

 {

     int res=;

     for (int i=x;i!=;i=fa[i])

     {

         if (dis(x,i)<=p)res+=query(p-dis(x,i),,n-,ra[i]);

         if (fa[i]&&dis(x,fa[i])<=p)res-=query(p-dis(x,fa[i]),,n-,rb[i]);

     }

     return res;

 }

 void dfs(int u,int par)

 {

     pos[u]=++tot,mn[][tot]=dep[u];

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (v==par) continue;

         dep[v]=dep[u]+,dfs(v,u),mn[][++tot]=dep[u];

     }

 }

 int main()

 {

     memset(hed,-,sizeof(hed));

     n=read(),m=read();

     for (int i=;i<=n;i++)

         value[i]=read();

     for (int i=;i<n;i++)

     {

         int x=read(),y=read();

         add(x,y),add(y,x);

     }

     dfs(,);

     for (int i=;i<=tot;i++)Log[i]=Log[i>>]+;

     for (int i=;(<<i)<=tot;i++)

         for (int j=;j<=tot-(<<i)+;j++)

             mn[i][j]=min(mn[i-][j],mn[i-][j+(<<(i-))]);

     f[]=<<,S=n;

     get_root(,),divide(rt);

     while(m--)

     {

         int flag=read(),x=read()^lastans,y=read()^lastans;

         if (flag)modify(x,y);

         else printf("%d\n",lastans=solve(x,y));

     }

 }