抄自：http://blog.csdn.net/coldef/article/details/61412577
当时看了就不会，看了别人的题解不懂怎么维护，最后抄了个代码.......
给定一棵n个点的树，每个点有颜色。m次询问,每次询问一个节点子树中深度和这个点深度之差<=d的点的颜色数量。多组数据,每组n,m<=10^5,总共小于500000
题解：如果不考虑深度，我们可以把相同颜色的节点按照dfs序排序，然后相邻节点在lca处-1，这样求子树和就可以求出答案了。考虑深度，我们就用主席树以深度为时间戳来维护呗。感觉看了原作者的代码学到了很多，原作者用set来维护相邻的相同颜色的节点真的妙。
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<set> #include<algorithm> #define mp(x,y) make_pair #define pa pair<int,int> #define itr set<pair<int,int> >::iterator #define MAXN 100000 using namespace std; int read() { int x=0,f=1;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 x*f; } int n,m,cnt,cc,dfn,head[MAXN+5],p[MAXN+5]; int fa[MAXN+5][25],rt[MAXN+5],dep[MAXN+5],nl[MAXN+5],nr[MAXN+5],col[MAXN+5]; struct TREE{ int l,r,x,lt,rt; }T[10000005]; vector<int> v[MAXN+5]; set<pa > ev[MAXN+5]; struct edge{ int to,next; }e[2*MAXN+5]; inline void ins(int f,int t){e[++cc].next=head[f];head[f]=cc;e[cc].to=t;} bool cmp(int x,int y){return nl[x]<nl[y];} bool cmp2(int x,int y){return dep[x]<dep[y];} void dfs(int x,int d) { dep[x]=d;nl[x]=++dfn; for(int i=head[x];i;i=e[i].next)dfs(e[i].to,d+1); nr[x]=dfn; } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y);int th=dep[x]-dep[y]; for(int i=0;th;th>>=1,++i)if(th&1)x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void renew(int x0,int&x,int k,int ad,int l,int r) { // cout<<"renew"<<x0<<" "<<x<<" "<<k<<" "<<ad<<" "<<l<<" "<<r<<endl; x=++cnt;T[x].lt=T[x0].lt;T[x].rt=T[x0].rt; T[x].l=l;T[x].r=r;T[x].x=T[x0].x+ad; if(l==r)return;int mid=(l+r)>>1; if(k<=mid)renew(T[x0].lt,T[x].lt,k,ad,l,mid); else renew(T[x0].rt,T[x].rt,k,ad,mid+1,r); } int query(int k,int l,int r) { //cout<<"query"<<k<<" "<<l<<" "<<r<<endl; if(!k)return 0; if(T[k].l==l&&T[k].r==r)return T[k].x; int mid=(T[k].l+T[k].r)>>1; if(r<=mid)return query(T[k].lt,l,r); else if(l>mid) return query(T[k].rt,l,r); else return query(T[k].lt,l,mid)+query(T[k].rt,mid+1,r); } int main() { int T=read(); for(int i=1;i<=T;i++) { cnt=cc=dfn=0;for(int i=1;i<=n;i++)v[i].clear(); memset(head,0,sizeof(head));memset(rt,0,sizeof(rt));n=read();m=read(); for(int i=1;i<=n;i++){col[i]=read();} for(int i=2;i<=n;i++){fa[i][0]=read();ins(fa[i][0],i);} dfs(1,1); for(int i=1;i<20;i++)for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=n;i++)p[i]=i;sort(p+1,p+n+1,cmp2); for(int i=1;i<=n;i++) { int x=p[i],y=p[i-1]; renew(rt[dep[y]],rt[dep[x]],nl[x],1,1,n); if(ev[col[x]].empty()){ev[col[x]].insert(pa(nl[x],x));continue;} ev[col[x]].insert(pa(nl[x],x)); itr it=ev[col[x]].find(pa(nl[x],x)); itr a=--it;it=ev[col[x]].find(pa(nl[x],x));itr b=++it; if(a!=ev[col[x]].end()&&b!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(a->second,b->second)],1,1,n); if(a!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(x,a->second)],-1,1,n); if(b!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(x,b->second)],-1,1,n); } int last=0; for(int i=1;i<=n;i++)ev[i].clear(); for(int i=1;i<=m;i++) { int u=read()^last,v=read()^last; last=query(rt[min(dep[p[n]],dep[u]+v)],nl[u],nr[u]); printf("%d ",last); } } return 0; }
我好菜啊都不会。