然后是\(O(n\log^2n)\)的
#include<cctype> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; const int N=80005; typedef double db; typedef long long ll; const int M=10000010; #define pb(A) push_back(A) #define pii std::pair<int,int> #define mp(A,B) std::make_pair(A,B) int s1[N<<1],s2[N<<1]; int n,m,cnt,tot,val[N],sze[N]; int k[N],x[N],y[N],g[N<<1],len; int ch[M][2],root[N],f[N][19]; int head[N],sum[M],dfn[N],d[N]; struct Edge{ int to,nxt; }edge[N<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } int getint(){ int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); return w?-X:X; } void dfs(int now){ sze[now]=1;dfn[now]=++tot; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(sze[to]) continue; f[to][0]=now;d[to]=d[now]+1; for(int j=1;j<=17;j++) f[to][j]=f[f[to][j-1]][j-1]; dfs(to);sze[now]+=sze[to]; } } void pushup(int cur){ sum[cur]=sum[ch[cur][0]]+sum[ch[cur][1]]; } void modify(int &cur,int ql,int c,int l=1,int r=len){ if(!cur) cur=++tot; if(l==r){sum[cur]+=c;return;} int mid=l+r>>1; if(ql<=mid) modify(ch[cur][0],ql,c,l,mid); else modify(ch[cur][1],ql,c,mid+1,r); pushup(cur); } void add(int x,int y,int z){ while(x<=n) modify(root[x],y,z),x+=x&-x; } int lca(int x,int y){ if(d[x]<d[y]) swap(x,y); for(int i=17;~i;i--) if(d[f[x][i]]>=d[y]) x=f[x][i]; if(x==y) return x; for(int i=17;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int query(int k,int l=1,int r=len){ if(l==r) return l; int now=0,mid=l+r>>1; for(int i=1;i<=s1[0];i++) now+=sum[ch[s1[i]][1]]; for(int i=1;i<=s2[0];i++) now-=sum[ch[s2[i]][1]]; if(now>=k){ for(int i=1;i<=s1[0];i++) s1[i]=ch[s1[i]][1]; for(int i=1;i<=s2[0];i++) s2[i]=ch[s2[i]][1]; return query(k,mid+1,r); } else{ for(int i=1;i<=s1[0];i++) s1[i]=ch[s1[i]][0]; for(int i=1;i<=s2[0];i++) s2[i]=ch[s2[i]][0]; return query(k-now,l,mid); } } void ask(int k,int a,int b){ int c=lca(a,b),dd=f[c][0];s1[0]=s2[0]=0; if(d[a]+d[b]-d[c]-d[dd]<k) {printf("invalid request!\n");return;} for(int i=dfn[a];i;i-=i&-i) s1[++s1[0]]=root[i]; for(int i=dfn[b];i;i-=i&-i) s1[++s1[0]]=root[i]; for(int i=dfn[c];i;i-=i&-i) s2[++s2[0]]=root[i]; for(int i=dfn[dd];i;i-=i&-i) s2[++s2[0]]=root[i]; printf("%d\n",g[query(k)]); } signed main(){ n=getint(),m=getint(); for(int i=1;i<=n;i++) val[i]=getint(),g[++len]=val[i]; for(int i=1;i<n;i++){ int x=getint(),y=getint(); add(x,y);add(y,x); } for(int i=1;i<=m;i++){ k[i]=getint(),x[i]=getint(),y[i]=getint(); if(!k[i]) g[++len]=y[i]; } std::sort(g+1,g+1+len);len=std::unique(g+1,g+1+len)-g-1; for(int i=1;i<=n;i++) val[i]=std::lower_bound(g+1,g+1+len,val[i])-g; for(int i=1;i<=m;i++) if(!k[i]) y[i]=std::lower_bound(g+1,g+1+len,y[i])-g; d[1]=1;dfs(1);tot=0; for(int i=1;i<=n;i++) add(dfn[i],val[i],1),add(dfn[i]+sze[i],val[i],-1); for(int i=1;i<=m;i++){ if(!k[i]) add(dfn[x[i]],val[x[i]],-1),add(dfn[x[i]]+sze[x[i]],val[x[i]],1),val[x[i]]=y[i],add(dfn[x[i]],val[x[i]],1),add(dfn[x[i]]+sze[x[i]],val[x[i]],-1); else ask(k[i],x[i],y[i]); } return 0; }