用的是莫队+值域分块，WA on #1。

#include<bits/stdc++.h>
#ifdef WIN32
#define getc() getchar()
#else
#define getc() getchar_unlocked()
#endif
#define N 80005
using namespace std;
struct query{
    int k,l,r,t,id;
}q1[N];
struct update{
    int p,c;
}q2[N];
int n,m,q,block_size,B,len,ccnt,qcnt,rcnt,size;
int h[N],a[N<<1],c[N<<1],f[N],g[N],fa[N][25],dep[N],cnt1[405],cnt2[N<<1],ans[N];
vector<int>s[N];
bitset<N<<1>vis;
void read(int &n){
    n=0;bool neg=false;
    char c=getc();
    while(c<'0'||c>'9') neg^=c=='-',c=getc();
    while(c>='0'&&c<='9') n=(n<<1)+(n<<3)+(c^48),c=getc();
    n=neg?-n:n;
}
void print(int x){
    if(!x) return putchar('0'),void();
    if(x<0) putchar('-'),x=-x;
    int top=0,a[20];
    while(x) a[top++]=x%10,x/=10;
    while(top) putchar(a[--top]+'0');
}
void dfs(int x,int fafa){
    a[f[x]=++len]=x,dep[x]=dep[fafa]+1;
    for(auto p:s[x]){
        if(p==fafa) continue;
        fa[p][0]=x,dfs(p,x);
    }
    a[g[x]=++len]=x;
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    if(dep[x]!=dep[y])
        for(int i=20;i>=0;i--){
            int v=fa[x][i];
            if(dep[v]>=dep[y]) x=v;
        }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        int vx=fa[x][i],vy=fa[y][i];
        if(vx!=vy) x=vx,y=vy;
    }
    return fa[x][0];
}
void sol(int x){
    if(vis[x]) cnt1[h[x]/block_size]--,cnt2[h[x]]--;
    else cnt1[h[x]/block_size]++,cnt2[h[x]]++;
    vis[x]=!vis[x];
}
bool cmp(query x,query y){
    if(x.l/B^y.l/B) return x.l<y.l;
    if(x.r/B^y.r/B) return (x.l/B&1)?x.r<y.r:x.r>y.r;
    return x.t<y.t;
}
int main(){
    read(n),read(q);
    for(int i=1;i<=n;i++) read(h[i]),c[++ccnt]=h[i];
    for(int i=1,a,b;i<n;i++){
        read(a),read(b);
        s[a].push_back(b);
        s[b].push_back(a);
    }
    dfs(1,0);
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    for(int i=1,k,x,y;i<=q;i++){
        read(k),read(x),read(y);
        if(!k) q2[++rcnt]={x,y},c[++ccnt]=y;
        else{
            if(f[x]>f[y]) swap(x,y);
            q1[++qcnt]={k,LCA(x,y)==x?f[x]:g[x],f[y],rcnt,qcnt};
        }
    }
    sort(c+1,c+ccnt+1);
    ccnt=unique(c+1,c+ccnt+1)-c-1;
    B=ceil(pow(len,2.0/3));
    block_size=ceil(sqrt(ccnt));
    for(int i=1;i<=n;i++) h[i]=lower_bound(c+1,c+ccnt+1,h[i])-c;
    for(int i=1;i<=rcnt;i++) q2[i].c=lower_bound(c+1,c+ccnt+1,q2[i].c)-c;
    int lenb=(ccnt-1)/block_size+1;
    sort(q1+1,q1+qcnt+1,cmp);
    for(int i=1,l=1,r=0,t=0;i<=qcnt;i++){
        auto p=q1[i];
        while(l>p.l) sol(a[--l]);
        while(r<p.r) sol(a[++r]);
        while(l<p.l) sol(a[l++]);
        while(r>p.r) sol(a[r--]);
        while(t<p.t){
            t++;
            int u=q2[t].p;
            if(!vis[u]) swap(h[u],q2[t].c);
            else sol(u),swap(h[u],q2[t].c),sol(u); 
        }
        while(t>p.t){
            int u=q2[t].p;
            if(!vis[u]) swap(h[u],q2[t].c);
            else sol(u),swap(h[u],q2[t].c),sol(u); 
            t--;
        }
        int u=a[l],v=a[r],lca=LCA(u,v);
        if(u!=lca&&v!=lca) sol(lca);
        int k=p.k;
        for(int i=lenb-1;i>=0;i--){
            if(k>cnt1[i]) k-=cnt1[i];
            else{
                for(int j=(i+1)*block_size-1;j>=i*block_size;j--){
                    if(j>ccnt) continue;
                    if(cnt2[j]){
                        if(k<=cnt2[j]){ans[p.id]=j;break;}
                        k-=cnt2[j];
                    }
                }
                break;
            }
        }
        if(u!=lca&&v!=lca) sol(lca);
    }
    for(int i=1;i<=qcnt;i++){
        if(!ans[i]) puts("invalid request!");
        else print(c[ans[i]]),puts("");
    }
    return 0;
}