一些套路的综合应用:
要求第k大,主席树。
要查两点间路径,处理到根的前缀和,求出lca后差分。
要带修,发现每次改的是子树。那么可以考虑dfs序,就成了每次改区间。
改区间,再差分一下就成了单点修改查询前缀。直接上树套树即可。
(其实写这篇题解是因为被我自己写的树套树优美到了,谁说树套树只能恶心码量大?)

#include<bits/stdc++.h>
using namespace std;
const int N=8e4+50,M=2e7+50,K=1e8;
int n,q,a[N],ver[N*2],nxt[N*2],head[N],tot,f[N][17],d[N],dfn[N],rr[N],cnt,r[N];
int lc[M],rc[M],sum[M];
struct node{
    int n,a[N];
    int calc(){int ret=0;for(int i=1;i<=n;i++)ret+=sum[rc[a[i]]];return ret;}
    void L(){for(int i=1;i<=n;i++)a[i]=lc[a[i]];}
    void R(){for(int i=1;i<=n;i++)a[i]=rc[a[i]];}
    void init(int x){n=0;for(;x;x-=x&-x)a[++n]=r[x];}
}A,B,C,D;
int in(){
    int x=0,c;
    while(!isdigit(c=getchar()));
    while(isdigit(c))x=x*10+(c^48),c=getchar();
    return x;
}
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs(int x,int ff){
    f[x][0]=ff;d[x]=d[ff]+1;dfn[x]=++cnt;
    for(int i=0;i<16;i++)f[x][i+1]=f[f[x][i]][i];
    for(int i=head[x],y;i;i=nxt[i])if((y=ver[i])!=ff)dfs(y,x);
    rr[x]=cnt;
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=16;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=16;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void change(int &x,int l,int r,int p,int d){
    if(!x)x=++cnt;sum[x]+=d;
    if(l==r)return;int mid=(l+r)>>1;
    if(p<=mid)change(lc[x],l,mid,p,d);
    else change(rc[x],mid+1,r,p,d);
}
void change(int x,int p,int d){for(;x<=n;x+=x&-x)change(r[x],1,K,p,d);}
int query(int l,int r,int d){
    if(l==r)return l;
    int mid=(l+r)>>1,dat=A.calc()+B.calc()-C.calc()-D.calc();
    if(dat>=d){A.R(),B.R(),C.R(),D.R();return query(mid+1,r,d);}
    A.L(),B.L(),C.L(),D.L();return query(l,mid,d-dat);
}
int main(){
    n=in();q=in();
    for(int i=1;i<=n;i++)a[i]=in();
    for(int i=1,x,y;i<n;i++)add(x=in(),y=in()),add(y,x);
    dfs(1,0);cnt=0;
    for(int i=1;i<=n;i++)change(dfn[i],a[i],1),change(rr[i]+1,a[i],-1);
    for(int i=1,k,x,y;i<=q;i++){
        k=in();x=in();y=in();
        if(k){
            int z=lca(x,y);
            if(d[x]+d[y]-2*d[z]+1<k){puts("invalid request!");continue;}
            A.init(dfn[x]);B.init(dfn[y]);C.init(dfn[z]);D.init(dfn[f[z][0]]);
            printf("%d\n",query(1,K,k));
        }
        else change(dfn[x],a[x],-1),change(rr[x]+1,a[x],1),change(dfn[x],a[x]=y,1),change(rr[x]+1,y,-1);
    }
    return 0;
}