树链的并+STL-set+DFS序+可持久化线段树
如果没有深度限制，那么对于一种颜色，子树内包含该颜色的节点为：所有该颜色节点到根节点路径覆盖的所有节点，即树链的并。
因此对于每一种颜色求树链的并，支持链加操作；查询单个点的时候就是查询单点值。树上差分后转变为单点加、子树求和，使用DFS序转化为区间问题后使用数据结构维护。
那么有深度限制呢？我们按照深度维护可持久化线段树，第 $i$ 个版本我们只考虑深度小于等于 $i$ 的节点的影响。此时需要使用STL-set维护每个颜色的树链的并。
查询时直接查询depth[x]+d版本对应的可持久化线段树中，x节点子树内的权值和即可。
时间复杂度 $O(n\log n)$ 。
关于树链合并：
按dfn序排好序后，
所有点到根距离-所有相邻两点lca到根距离为树链的并总长
sort(que+1,que+n+1,cmp);
for(i=1;i<=n;i++) res+=dis[que[i]];
for(i=1;i<=n;i++) res-=dis[LCA(que[i],que[i+1])];如图：
dfn序为anc,x,y,z
求x,y,z树链的并：dis[anc]加3次减2次
求x,y,z,anc树链的并：dis[anc]加4次减3次（LCA(anc,x)=anc）
可以树链的并求和
也可以树链的并修改
可以解决子树不同数问题
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define mid (l+r>>1) 7 #define gc() getchar() 8 #define ms(i,a) memset(a,i,sizeof(a)) 9 template<class T>void read(T &x){ 10 x=0; char c=0; 11 while (!isdigit(c)) c=gc(); 12 while (isdigit(c)) x=x*10+(c^48),c=gc(); 13 } 14 int const N=100000+3; 15 int n,m,rt[N],d[N],f[N][17],lc[N*40],rc[N*40],s[N*40],cnt,sum,tin[N],tout[N],tot,H[N],c[N],pos[N]; 16 set<int> se[N]; 17 set<int> :: iterator it; 18 struct Edge{ 19 int to,nt; 20 }E[N]; 21 struct node{ 22 int id,dp; 23 bool operator < (const node &rhs) const { return dp<rhs.dp;} 24 }a[N]; 25 void add(int a,int b){ 26 E[++cnt]=(Edge){b,H[a]}; H[a]=cnt; 27 } 28 void dfs(int x,int fa){ 29 f[x][0]=fa; 30 d[x]=d[f[x][0]]+1; 31 tin[x]=++tot; pos[tot]=x; 32 rep(j,1,16) f[x][j]=f[f[x][j-1]][j-1]; 33 for(R i=H[x]; i; i=E[i].nt){ 34 int v=E[i].to; 35 dfs(v,x); 36 } 37 tout[x]=tot; 38 } 39 void update(int old,int &x,int p,int l,int r,int v){ 40 x=++sum; lc[x]=lc[old]; rc[x]=rc[old]; s[x]=s[old]+v; 41 if(l==r) return ; 42 if(p<=mid) update(lc[old],lc[x],p,l,mid,v); 43 else update(rc[old],rc[x],p,mid+1,r,v); 44 } 45 int lca(int x,int y){ 46 if(d[x]<d[y]) swap(x,y); 47 Rep(i,16,0) if((1<<i)<=d[x]-d[y]) x=f[x][i]; 48 if(x==y) return x; 49 Rep(i,16,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 50 return f[x][0]; 51 } 52 int query(int x,int l,int r,int ll,int rr){ 53 if (!x) return 0; 54 if(ll<=l && r<=rr) return s[x]; 55 int t1=0,t2=0; 56 if(ll<=mid) t1=query(lc[x],l,mid,ll,rr); 57 if(rr>mid) t2=query(rc[x],mid+1,r,ll,rr); 58 return t1+t2; 59 } 60 61 int main(){ 62 int T; read(T); 63 while (T--){ 64 read(n); 65 read(m); 66 cnt=tot=sum=0; 67 ms(0,H);ms(0,rt); 68 rep(i,1,n) read(c[i]); 69 rep(i,2,n) { 70 int x; read(x); 71 add(x,i); 72 } 73 dfs(1,0); 74 rep(i,1,n) a[i].id=i,a[i].dp=d[i]; 75 sort(a+1,a+n+1); 76 rep(i,1,n) se[i].clear(); 77 int p=1; 78 rep(i,1,n) { 79 rt[i]=rt[i-1]; 80 while (p<=n && a[p].dp<=i) { 81 update(rt[i],rt[i],tin[a[p].id],1,n,1); 82 it=se[c[a[p].id]].lower_bound(tin[a[p].id]); 83 int x=0,y=0; 84 if(it!=se[c[a[p].id]].end()) x=pos[*it]; 85 if(it!=se[c[a[p].id]].begin()) y=pos[*(--it)]; 86 if(x) update(rt[i],rt[i],tin[lca(x,a[p].id)],1,n,-1); 87 if(y) update(rt[i],rt[i],tin[lca(y,a[p].id)],1,n,-1); 88 if(x && y) update(rt[i],rt[i],tin[lca(x,y)],1,n,1); 89 se[c[a[p].id]].insert(tin[a[p].id]); 90 p++; 91 } 92 } 93 int last=0; 94 while (m--){ 95 int x,y; read(x); read(y); 96 x^=last; y=min(n,(y^last)+d[x]); 97 printf("%d\n",last=query(rt[y],1,n,tin[x],tout[x]) ); 98 } 99 } 100 return 0; 101 } 102 103 104
原文：https://www.cnblogs.com/ZJXXCN/p/10575770.html
