c/c++语言开发共享[bzoj4771] 七彩树

题意

给定一棵n个点，每个点带颜色的有根树。点的编号和颜色编号都在1到n，根的编号为1。m次询问，求x子树中与x距离边数不超过k的点中，颜色的种类数目。每个测试点有多组数据。

分析

不妨设1的父亲为0，0包含了所有颜色。不考虑深度限制，对于单独一种颜色c，易知颜色c对于任意两个色c的点之间的路径上的所有询问有且仅有一个贡献，利用树链的并（dfs序+树上差分）即可解决。

考虑深度约束，可以发现按深度对差分序列进行可持久化，使用线段树就可以了。

#include <bits/stdc++.h> using namespace std; const int n=500010;   struct node {     int ls,rs,val; } t[n*20]; int tot,root[n];   void insert(int&x,int y,int l,int r,int p,int w) {     t[x=++tot]=t[y];     t[x].val+=w; if(l==r) return;      int mid=(l+r)>>1;     if(p<=mid) insert(t[x].ls,t[y].ls,l,mid,p,w);     else insert(t[x].rs,t[y].rs,mid+1,r,p,w); } int query(int x,int l,int r,int l,int r) {     if(!x) return 0;     if(l<=l&&r<=r) return t[x].val;     int mid=(l+r)>>1, val=0;     if(l<=mid) val+=query(t[x].ls,l,mid,l,r);     if(mid<r) val+=query(t[x].rs,mid+1,r,l,r);     return val; }   int n,m,ndp,cnt; int val[n],siz[n],dfn[n],dep[n],fa[n][20]; vector<int> wuer[n]; queue<int> que;   struct mogic {     int x;      mogic(int x=0):x(x){}     bool operator<(const mogic&d) const {return dfn[x]<dfn[d.x];} }; set<mogic> d[n];   int lca(int x,int y) {     if(dep[x]<dep[y]) swap(x,y);     int dif=dep[x]-dep[y];     for(int i=19; ~i; --i) if((dif>>i)&1) x=fa[x][i];     if(x==y) return x;     for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i])          x=fa[x][i],y=fa[y][i];     return fa[x][0]; } void dfs(int x,int d) {     dfn[x]=++cnt;     dep[x]=dep[fa[x][0]=d]+(siz[x]=1);     for(int i=1; (1<<i)<=dep[x]; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];     for(int i=wuer[x].size()-1; ~i; --i) dfs(wuer[x][i],x),siz[x]+=siz[wuer[x][i]]; } void bfs() {     que.push(1);     while(que.size()) {         int x=que.front(); que.pop();         if(ndp!=dep[x]) {             root[ndp+1]=root[ndp];             ndp++;         }         insert(root[ndp],root[ndp],1,n,dfn[x],1);         set<mogic>::iterator k=d[val[x]].insert(mogic(x)).first;         set<mogic>::iterator k1=k,k2=k; k1--; k2++;         if(k!=d[val[x]].begin()&&k2!=d[val[x]].end()) insert(root[ndp],root[ndp],1,n,dfn[lca(k1->x,k2->x)],1);         if(k!=d[val[x]].begin()) insert(root[ndp],root[ndp],1,n,dfn[lca(k1->x,x)],-1);         if(k2!=d[val[x]].end()) insert(root[ndp],root[ndp],1,n,dfn[lca(x,k2->x)],-1);         for(int i=wuer[x].size()-1; ~i; --i) que.push(wuer[x][i]);     } }   int main() { //  freopen("a.in","r",stdin);     int t,last;     scanf("%d",&t);     while(t--) {         scanf("%d%d",&n,&m);         tot=cnt=last=ndp=0;         for(int i=1; i<=n; ++i) {             memset(fa[i],0,sizeof fa[i]);             scanf("%d",&val[i]);             wuer[i].clear();             d[i].clear();             root[i]=0;         }         for(int i=2,x; i<=n; ++i) {             scanf("%d",&x);             wuer[x].push_back(i);         }         dfs(1,0);          bfs();         for(int x,k; m--; ) {             scanf("%d%d",&x,&k); x^=last,k^=last;             printf("%dn",last=query(root[min(dep[x]+k,ndp)],1,n,dfn[x],dfn[x]+siz[x]-1));         }     }     return 0; }