在一片土地上有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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<vector>

using namespace std;

inline int read()

{

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

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

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

    return x*f;

}

#define MAXN 100010

int N,M,val[MAXN],lastans;

namespace Tree{

    struct EdgeNode{

        int next,to;

    }edge[MAXN<<1];

    int head[MAXN],cnt=1;

    inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

    inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}

    int deep[MAXN],dist[MAXN],father[18][MAXN];

    inline void DFS(int now,int last)

    {

        for (int i=1; i<=17; i++)

            if (deep[now]>=(1<<i))

                father[i][now]=father[i-1][father[i-1][now]];

            else

                break;

        for (int i=head[now]; i; i=edge[i].next)

            if (edge[i].to!=last) {

                deep[edge[i].to]=deep[now]+1;

                dist[edge[i].to]=dist[now]+1;

                father[0][edge[i].to]=now;

                DFS(edge[i].to,now);

            }

    }

    inline int LCA(int x,int y)

    {

        if (deep[x]<deep[y]) swap(x,y);

        int dd=deep[x]-deep[y];

        for (int i=0; i<=17; i++)

            if (dd&(1<<i)) x=father[i][x];

        for (int i=17; i>=0; i--)

            if (father[i][x]!=father[i][y])

                x=father[i][x],y=father[i][y];

        return x==y? x:father[0][x];

    }

    inline int Dist(int x,int y)

    {

        int z=LCA(x,y);

        return deep[x]+deep[y]-deep[z]-deep[z];

    }

}using namespace Tree;

namespace BIT{

    typedef vector<int> vec;

    struct BIT{

        vec tree; int n;

        inline void init(int size) {tree.resize(size+2); n=size+1;}

        inline int lowbit(int x) {return x&-x;}

        inline void Modify(int x,int d) {if (x<=0) return; for (int i=x; i<=n; i+=lowbit(i)) tree[i]+=d;}

        inline int Query(int x) {int re=0; if (x>n) x=n; for (int i=x; i>0; i-=lowbit(i)) re+=tree[i]; return re;}

    }f[MAXN],g[MAXN];

}using namespace BIT;

namespace TreeDivide{

    int size[MAXN],mx[MAXN],root,Sz,par[MAXN];

    bool visit[MAXN];

    inline void Getroot(int now,int last)

    {

        size[now]=1,mx[now]=0;

        for (int i=head[now]; i; i=edge[i].next)

            if (edge[i].to!=last && !visit[edge[i].to]) {

                Getroot(edge[i].to,now);

                size[now]+=size[edge[i].to];

                mx[now]=max(mx[now],size[edge[i].to]);

            }

        mx[now]=max(mx[now],Sz-size[now]);

        if (mx[now]<mx[root]) root=now;

    }

    inline void DFS(int now,int last,int dep)

    {

        f[root].Modify(dep+1,val[now]);

        g[par[root]].Modify(dep+1,val[now]);

        for (int i=head[now]; i; i=edge[i].next)

            if (edge[i].to!=last && !visit[edge[i].to]) {

                DFS(edge[i].to,now,dep+1);

            }

    }

    inline void Divide(int now)

    {

//      printf("Divide = %d\n",now);

        visit[now]=1;

        g[now].Modify(1,val[now]);

        for (int i=head[now]; i; i=edge[i].next)

            if (!visit[edge[i].to]) {

                root=0;

                Sz=size[edge[i].to];

                Getroot(edge[i].to,now);

                par[root]=now;

                f[root].init(Sz),g[root].init(Sz);

                DFS(edge[i].to,now,1);

                Divide(root);

            }

    }

    inline void Modify(int x,int y)

    {

        for (int i=x; i; i=par[i]) {

            int dep=Tree::Dist(x,i)+1;

            g[i].Modify(dep,y-val[x]);

            if (par[i])

                dep=Tree::Dist(par[i],x)+1,f[i].Modify(dep,y-val[x]);

        }

        val[x]=y;

    }

    inline int Query(int x,int k)

    {

        int ans=0;

        for (int i=x; i; i=par[i]) {

            int dep=k-Tree::Dist(x,i)+1;

            ans+=g[i].Query(dep);

            if (par[i])

                dep=k-Tree::Dist(x,par[i])+1,ans-=f[i].Query(dep);

        }

        return ans;

    }

}using namespace TreeDivide;

int main()

{

    N=read(),M=read();

    for (int i=1; i<=N; i++) val[i]=read();

    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),Tree::InsertEdge(x,y);

    Tree::DFS(1,0);

    Sz=mx[root=0]=N;

    Getroot(1,0);

    f[root].init(Sz),g[root].init(Sz);

    Divide(root);

    while (M--) {

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

        x^=lastans,y^=lastans;

        if (opt==1) {

            TreeDivide::Modify(x,y);

        } else {

            printf("%d\n",lastans=TreeDivide::Query(x,y));

        }

    }

    return 0;

}