求树上链的带修第k大，跟我上一篇的区间带修第k大其实思路差不多。区别见下。
只要先dfs一遍记录dfs序，就可以看成一个序列了。每个节点对应的线段树要维护从它到根的不同权值个数，所以每个节点会对以它为根的子树产生影响，所以树状数组修改时是区间修改而不再是单点修改。u到v的路径=u+v-lca(u,v)-lca(u,v)的父亲，所以查询时是四个位置一起跳。其他就没什么特别的了。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=80010,NN=160010; struct node{ int l,r,x; }tree[N*300]; struct odr{ int l,r; }d1[N]; struct opt{ int op,a,b; }q1[N]; struct numo{ int a,b,id; }a1[NN]; struct edge{ int y,next; }data[NN]; int n,q,num,num1,num2,cnt1,cnt2; int v[N],h[N],dep[N],fa[N][18],root[NN],lt[5][NN],tid[NN]; inline int read(){ int x=0,f=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f?-x:x; } inline void addedge(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num; } bool cmp1(numo i,numo j){ return i.a<j.a; } bool cmp2(numo i,numo j){ return i.id<j.id; } void add2(int &p,int pa,int pb,int x,int f){ if(!p){p=++num2;tree[p].l=tree[p].r=0;} tree[p].x+=f; if(pa==pb)return; int mid=(pa+pb)>>1; if(x<=mid)add2(tree[p].l,pa,mid,x,f); else add2(tree[p].r,mid+1,pb,x,f); } inline int lowbit(int x){ return x&(-x); } inline void add1(int x,int p,int f){ while(x<=n){ add2(root[x],1,cnt2,p,f); x+=lowbit(x); } } void dfs(int u,int f,int d){ dep[u]=d;fa[u][0]=f;d1[u].l=++num1; for(int i=h[u];i!=-1;i=data[i].next){ int v=data[i].y; if(v!=f)dfs(v,u,d+1); } d1[u].r=num1; } inline int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=17;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; if(x==y)return x; for(int i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];} return fa[x][0]; } inline void pre(int x1,int x2,int x3,int x4){ lt[1][0]=lt[2][0]=lt[3][0]=lt[4][0]=0; while(x1){lt[1][0]++;lt[1][lt[1][0]]=root[x1];x1-=lowbit(x1);} while(x2){lt[2][0]++;lt[2][lt[2][0]]=root[x2];x2-=lowbit(x2);} while(x3){lt[3][0]++;lt[3][lt[3][0]]=root[x3];x3-=lowbit(x3);} while(x4){lt[4][0]++;lt[4][lt[4][0]]=root[x4];x4-=lowbit(x4);} } int query(int a,int b,int k){ if(a==b)return a; int mid=(a+b)>>1,sum=0; for(int i=1;i<=lt[1][0];i++)sum+=tree[tree[lt[1][i]].r].x; for(int i=1;i<=lt[3][0];i++)sum-=tree[tree[lt[3][i]].r].x; for(int i=1;i<=lt[2][0];i++)sum+=tree[tree[lt[2][i]].r].x; for(int i=1;i<=lt[4][0];i++)sum-=tree[tree[lt[4][i]].r].x; if(sum>=k){ for(int i=1;i<=lt[1][0];i++)lt[1][i]=tree[lt[1][i]].r; for(int i=1;i<=lt[3][0];i++)lt[3][i]=tree[lt[3][i]].r; for(int i=1;i<=lt[2][0];i++)lt[2][i]=tree[lt[2][i]].r; for(int i=1;i<=lt[4][0];i++)lt[4][i]=tree[lt[4][i]].r; return query(mid+1,b,k); }else{ for(int i=1;i<=lt[1][0];i++)lt[1][i]=tree[lt[1][i]].l; for(int i=1;i<=lt[3][0];i++)lt[3][i]=tree[lt[3][i]].l; for(int i=1;i<=lt[2][0];i++)lt[2][i]=tree[lt[2][i]].l; for(int i=1;i<=lt[4][0];i++)lt[4][i]=tree[lt[4][i]].l; return query(a,mid,k-sum); } } int main(){ n=read();q=read(); for(int i=1;i<=n;i++){a1[i].a=read();a1[i].id=i;}cnt1=n; memset(h,-1,sizeof h);num=0; for(int x,y,i=1;i<n;i++){ x=read();y=read(); addedge(x,y);addedge(y,x); } num1=0;dep[0]=fa[0][0]=0;dfs(1,0,1); for(int i=1;i<=17;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=q;i++){ q1[i].op=read(); if(q1[i].op==0){ q1[i].a=read(); a1[++cnt1].a=q1[i].b=read(); a1[cnt1].id=cnt1; }else{q1[i].a=read();q1[i].b=read();} } sort(a1+1,a1+cnt1+1,cmp1); cnt2=1;a1[1].b=v[a1[1].id]=1;tid[1]=a1[1].a; for(int i=2;i<=cnt1;i++){ if(a1[i].a!=a1[i-1].a){cnt2++;tid[cnt2]=a1[i].a;} a1[i].b=v[a1[i].id]=cnt2; } sort(a1+1,a1+cnt1+1,cmp2); num2=0; for(int i=1;i<=n;i++){add1(d1[i].l,v[i],1);add1(d1[i].r+1,v[i],-1);} for(int cnt3=n,i=1;i<=q;i++){ if(q1[i].op==0){ add1(d1[q1[i].a].l,v[q1[i].a],-1); add1(d1[q1[i].a].r+1,v[q1[i].a],1); v[q1[i].a]=a1[++cnt3].b; add1(d1[q1[i].a].l,v[q1[i].a],1); add1(d1[q1[i].a].r+1,v[q1[i].a],-1); }else{ int l=lca(q1[i].a,q1[i].b); if(dep[q1[i].a]+dep[q1[i].b]-2*dep[l]+1<q1[i].op){ printf("invalid request!\n");continue; }pre(d1[q1[i].a].l,d1[q1[i].b].l,d1[l].l,d1[fa[l][0]].l); printf("%d\n",tid[query(1,cnt2,q1[i].op)]); } } return 0; }
