以前看到这题以为不可写，树链剖分+线段树套平衡树，3个log了还不如去写暴力。。。

然而仔细分析一下就是下面这样：

如果不带修改，就是Spoj 10628. Count on a tree

如果不是树是序列带修改，就是Zju2112 Dynamic Rankings

然后怎么做呢？

先把COT给做完，假设没修改只有询问的话；

然后处理出这颗树的dfs序，当我们对其中某一个点修改点权的时候，相当于把它子树内所有点的主席树所存的信息全部修改，对应到dfs序上就是一段区间，所以就要支持区间删减一个数；

想到了什么？就是ZJU那题！

所以现在已经很明了了，我们把两个部分（初始点权，修改后的点权）分开来记，前一部分用正常的主席树，后一部分用树状数组套主席树来进行前缀和优化。

/**************************************************************
    Problem: 1146
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1648 ms
    Memory:87964 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 80010
#define mid (l+r>>1)
int n,q,et=1,la[N],v[N],cnt=1,tot,y[N<<1],top[N],dfn,L[N],R[N],fa[N],son[N],siz[N],dep[N],root[N],tr[N],tmp0[N],tmp1[N],ltot,rtot;
struct E{int to,nxt;}e[N<<1];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
struct Q{int k,a,b;}a[N];
struct D{int x,n;}d[N<<1];
bool operator<(const D&a,const D&b){return a.x<b.x;}
struct T{int ls,rs,cnt;}t[N*83];
int bt(int g,int l,int r,int v,int p){
    int o=++tot;t[o]=t[g],t[o].cnt+=p;
    if(l<r)if(v<=mid)t[o].ls=bt(t[g].ls,l,mid,v,p);
    else t[o].rs=bt(t[g].rs,mid+1,r,v,p);
    return o;
}
void add(int x,int v,int p){
    for(;x<=n;x+=x&-x)tr[x]=bt(tr[x],1,cnt,v,p);
}
void dfs(int x,int f){
    siz[x]=1,dep[x]=dep[fa[x]=f]+1;
    for(int i=la[x];i;i=e[i].nxt)if(e[i].to!=f){
        dfs(e[i].to,x),siz[x]+=siz[e[i].to];
        if(siz[son[x]]<siz[e[i].to])son[x]=e[i].to;
    }
}
void dfs2(int x,int tp){
    top[x]=tp,L[x]=++dfn,root[x]=bt(root[fa[x]],1,cnt,v[x],1);
    if(son[x])dfs2(son[x],tp);
    for(int i=la[x];i;i=e[i].nxt)
    if(e[i].to!=fa[x]&&e[i].to!=son[x])dfs2(e[i].to,e[i].to);
    R[x]=dfn;
}
int lca(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
void get(int x,int k){
    if(k){for(x?tmp1[++rtot]=root[x]:1,x=L[x];x;x-=x&-x)if(tr[x])tmp1[++rtot]=tr[x];}
    else {for(x?tmp0[++ltot]=root[x]:1,x=L[x];x;x-=x&-x)if(tr[x])tmp0[++ltot]=tr[x];}
}
int query(int k,int l,int r){
    int sum;
    while(l<r){
        sum=0;
        for(int i=1;i<=ltot;i++)sum-=t[t[tmp0[i]].rs].cnt;
        for(int i=1;i<=rtot;i++)sum+=t[t[tmp1[i]].rs].cnt;
        if(sum>=k){
            for(int i=1;i<=ltot;i++)tmp0[i]=t[tmp0[i]].rs;
            for(int i=1;i<=rtot;i++)tmp1[i]=t[tmp1[i]].rs;
            l=mid+1;
        }else{
            for(int i=1;i<=ltot;i++)tmp0[i]=t[tmp0[i]].ls;
            for(int i=1;i<=rtot;i++)tmp1[i]=t[tmp1[i]].ls;
            r=mid,k-=sum;
        }
    }
    return l;
}
int main(){
    n=F(),q=F();
    for(int i=1;i<=n;i++)d[++tot]=(D){v[i]=F(),i};
    for(int i=1,g,h;i<n;i++)g=F(),h=F(),adde(g,h),adde(h,g);
    for(int i=1;i<=q;i++)a[i]=(Q){F(),F(),F()},!a[i].k?d[++tot]=(D){a[i].b,i+n},1:1;
    std::sort(d+1,d+1+tot);d[tot+1].x=-1;
    for(int i=1;i<=tot;i++){
        if(d[i].n<=n)v[d[i].n]=cnt;else a[d[i].n-n].b=cnt;
        if(d[i].x!=d[i+1].x)y[cnt++]=d[i].x;
    }
    cnt--,tot=0,dfs(1,0),dfs2(1,1);
    for(int i=1,xx,yy,zz;i<=q;i++)
    if(!a[i].k){
        add(L[a[i].a],v[a[i].a],-1),add(R[a[i].a]+1,v[a[i].a],1);v[a[i].a]=a[i].b;
        add(L[a[i].a],v[a[i].a],1),add(R[a[i].a]+1,v[a[i].a],-1);
    }else{
        xx=a[i].a,yy=a[i].b,zz=lca(xx,yy);
        if(dep[xx]+dep[yy]-dep[zz]*2+1<a[i].k)puts("invalid request!");
        else{
            ltot=rtot=0,get(xx,1),get(yy,1),get(zz,0),get(fa[zz],0);
            printf("%d\n",y[query(a[i].k,1,cnt)]);
        }
    }
}