题解 P4175 【[CTSC2008]网络管理】

动态树上路径第k大，~~我们自然可以想到树剖套树套树乱搞~~ 动态区间第k大主要就是两种写法：树套树和整体二分。 那么树上路径第k大，我们也可以考虑使用整体二分。 我们对值域进行整体二分，那么接下来的问题就是如何求一条路径上值在 $[l,r]$ 上的点的个数。 我们可以用树上差分的思想，把问题转化成从 $i$ 到根节点的路径上有几个值在 $[l,r]$ 上的点。 那么当我们要在 $i$ 处加入一个点的时候，所有在 $i$ 子树里的点，到根节点的路径上的满足条件的点都会增加1。 所以我们求一下dfn之后问题就转化成了区间修改单点查询，树状数组实现。 代码难度也不大。 复杂度 $O(n\log^2n)$ ```cpp # include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(register int i=a;i<=b;i++) # define _Rep(i,a,b) for(register int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=2e5+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int n,m,q; int head[N],cnt; int a[N],faz[N]; int dfn[N],dfsxu,siz[N]; int f[N][20],dep[N]; int bit[N]; int del[N]; int out[N],qc; struct Edge{ int to,next; }e[N<<1]; void addedge(int x,int y){ e[++cnt]=(Edge){y,head[x]},head[x]=cnt; } struct misaka{ int x,y,z,k,id; }T[N],T1[N],T2[N]; void add(int o,int x){ for(;o<=n;o+=o&-o)bit[o]+=x; } int ask(int o){ int res=0; for(;o;o-=o&-o)res+=bit[o]; return res; } void dfs(int u,int fa){ dfn[u]=++dfsxu; siz[u]=1; f[u][0]=fa; Rep(i,1,19)f[u][i]=f[f[u][i-1]][i-1]; dep[u]=dep[fa]+1; faz[u]=fa; RepG(i,u){ int v=e[i].to; if(v==fa)continue; dfs(v,u); siz[u]+=siz[v]; } } int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); _Rep(i,19,0)if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; _Rep(i,19,0)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } void solve(int l,int r,int L,int R){ if(l==r){ Rep(i,L,R) if(T[i].k) out[T[i].id]=l; return; } int mid=l+r>>1; int cnt1=0,cnt2=0,top=0; Rep(i,L,R) if(!T[i].k) if(T[i].y<=mid){ add(dfn[T[i].x],T[i].z); add(dfn[T[i].x]+siz[T[i].x],-T[i].z); T1[++cnt1]=T[i]; del[++top]=i; } else T2[++cnt2]=T[i]; else{ int lft=ask(dfn[T[i].x])+ask(dfn[T[i].y])-ask(dfn[T[i].z]); if(faz[T[i].z])lft-=ask(dfn[faz[T[i].z]]); if(T[i].k<=lft)T1[++cnt1]=T[i]; else{ T[i].k-=lft; T2[++cnt2]=T[i]; } } Rep(i,1,top){ int x=T[del[i]].x,z=T[del[i]].z; add(dfn[x],-z),add(dfn[x]+siz[x],z); } Rep(i,1,cnt1)T[L+i-1]=T1[i]; Rep(i,1,cnt2)T[L+cnt1+i-1]=T2[i]; solve(l,mid,L,L+cnt1-1); solve(mid+1,r,L+cnt1,R); } int main() { memset(head,-1,sizeof(head)); read(n),read(q); Rep(i,1,n){ read(a[i]); T[++m]=(misaka){i,a[i],1,0,0}; } Rep(i,1,n-1){ int x,y; read(x),read(y); addedge(x,y),addedge(y,x); } dfs(1,0); while(q--){ int opt,x,y; read(opt),read(x),read(y); if(!opt){ T[++m]=(misaka){x,a[x],-1,0,0}; a[x]=y; T[++m]=(misaka){x,a[x],1,0,0}; } else{ int z=lca(x,y); int len=dep[x]+dep[y]-2*dep[z]+1; if(len<opt)out[++qc]=-1; else T[++m]=(misaka){x,y,z,len-opt+1,++qc}; } } solve(1,1e8,1,m); Rep(i,1,qc) if(~out[i])printf("%d\n",out[i]); else puts("invalid request!"); return 0; } ```