题目大意
给定一棵树，支持两种操作:将一个点染黑，询问路径上在$k$步操作前就已经被染黑的点的数量。
题解
将染黑看做给一个点赋其操作编号点权，每次询问路径上点权小于一定值的数量。
这样会有一个性质，由于$k>0$，所以我们完全可以在查询之前将所有点权赋上。
所以只需要离线然后查询就好了，可以在树上利用差分主席树维护。
#include#include #include #include #include #include #define LL long long#define M 300020using namespace std;namespace IO{ const int BS=(1<<20); int Top=0; char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1; char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return *HD++;} void flush(){fwrite(OT,1,OS-OT,stdout);} void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;} void write(int x){ if(!x){Putchar('0');return;} while(x) SS[++Top]=x%10,x/=10; while(Top) Putchar(SS[Top]+'0'),--Top; } int read(){ int nm=0,fh=1; char cw=Getchar(); for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh; for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0'); return nm*fh; }}using namespace IO;int n,m,rt[M],L[M*22],R[M*22],sum[M*22],fs[M],nt[M],to[M],tmp,cnt;int sz[M],mxs[M],tp[M],fa[M],dep[M],Root,u[M],v[M],c[M],T,col[M];void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;}void ins(int &x,int pre,int l,int r,int pos){ x=++cnt,L[x]=L[pre],R[x]=R[pre]; sum[x]=sum[pre]+1; if(l==r) return; int mid=((l+r)>>1); if(pos<=mid) ins(L[x],L[pre],l,mid,pos); else ins(R[x],R[pre],mid+1,r,pos);}int calc(int t1,int t2,int d1,int d2){return sum[t1]+sum[t2]-sum[d1]-sum[d2];}int qry(int t1,int t2,int d1,int d2,int l,int r,int pos){ int now=calc(t1,t2,d1,d2),mid=((l+r)>>1); if(l>=pos||!now) return 0; if(r