如果没有修改就是简单主席树，有了修改的话因为主席树维护的是到根的一段路径，所以修改操作会修改子树，也就是连续的一段dfn
所以显然树套树一波就没了
极其好写
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n;
int W[80010],w[160010],m;
int K[80010],A[80010],B[80010],dep[80010];
int fir[80010],dis[160010],nxt[160010],id;
il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
int dfn[80010],siz[80010];
int rt[80010],ls[10000010],rs[10000010],sum[10000010],cnt;
int st[17][80010];
il vd dfs(int x,int fa=-1){
dfn[x]=++dfn[0];siz[x]=1;
for(int i=fir[x];i;i=nxt[i]){
if(dis[i]==fa)continue;
st[0][dis[i]]=x;
dep[dis[i]]=dep[x]+1;
dfs(dis[i],x);
siz[x]+=siz[dis[i]];
}
}
#define mid ((l+r)>>1)
il vd update(int&x,int l,int r,const int&p,const int&d){
if(!x)x=++cnt;sum[x]+=d;if(l==r)return;
if(p<=mid)update(ls[x],l,mid,p,d);
else update(rs[x],mid+1,r,p,d);
}
#undef mid
il vd Update(int l,int r,int w,int d){
while(l<=n)update(rt[l],1,m,w,d),l+=l&-l;
while(r<=n)update(rt[r],1,m,w,-d),r+=r&-r;
}
il int LCA(int x,int y){
if(dep[x]<dep[y])std::swap(x,y);
int C=dep[x]-dep[y];
for(int i=16;~i;--i)if(C&(1<<i))x=st[i][x];
for(int i=16;~i;--i)if(st[i][x]^st[i][y])x=st[i][x],y=st[i][y];
if(x^y)x=st[0][x];return x;
}
int main(){
n=gi();
int q=gi(),x,y;
for(int i=1;i<=n;++i)W[i]=w[++m]=gi();
for(int i=1;i<n;++i)x=gi(),y=gi(),link(x,y),link(y,x);
for(int i=1;i<=q;++i){
K[i]=gi(),A[i]=gi(),B[i]=gi();
if(!K[i])w[++m]=B[i];
}
std::sort(w+1,w+m+1),m=std::unique(w+1,w+m+1)-w-1;
for(int i=1;i<=n;++i)W[i]=std::lower_bound(w+1,w+m+1,W[i])-w;
for(int i=1;i<=q;++i)if(!K[i])B[i]=std::lower_bound(w+1,w+m+1,B[i])-w;
dfs(1);
for(int i=1;i<17;++i)
for(int j=1;j<=n;++j)
st[i][j]=st[i-1][st[i-1][j]];
for(int i=1;i<=n;++i)Update(dfn[i],dfn[i]+siz[i],W[i],1);
for(int i=1;i<=q;++i)
if(K[i]){
x=A[i],y=B[i];int lca=LCA(x,y);
if(dep[x]+dep[y]-2*dep[lca]+1<K[i]){puts("invalid request!");continue;}
static int A[2333],B[2333],a,b;
a=b=0;
int l,r;
r=dfn[x];while(r)B[++b]=rt[r],r-=r&-r;
r=dfn[y];while(r)B[++b]=rt[r],r-=r&-r;
r=dfn[lca];while(r)A[++a]=rt[r],r-=r&-r;
if(lca!=1){r=dfn[st[0][lca]];while(r)A[++a]=rt[r],r-=r&-r;}
l=1,r=m;
while(l^r){
int tot=0;
for(int i=1;i<=a;++i)tot-=sum[rs[A[i]]];
for(int i=1;i<=b;++i)tot+=sum[rs[B[i]]];
if(K[i]>tot){
K[i]-=tot;
for(int i=1;i<=a;++i)A[i]=ls[A[i]];
for(int i=1;i<=b;++i)B[i]=ls[B[i]];
r=(l+r)>>1;
}else{
for(int i=1;i<=a;++i)A[i]=rs[A[i]];
for(int i=1;i<=b;++i)B[i]=rs[B[i]];
l=((l+r)>>1)+1;
}
}
printf("%d\n",w[l]);
}else Update(dfn[A[i]],dfn[A[i]]+siz[A[i]],W[A[i]],-1),Update(dfn[A[i]],dfn[A[i]]+siz[A[i]],W[A[i]]=B[i],1);
return 0;
}