BZOJ4771七彩树——可持久化线段树+set+树链的并+LCA-白红宇

BZOJ4771七彩树——可持久化线段树+set+树链的并+LCA

阅读量：6585 次

发布时间：2019-06-24

本文共 3678 字，大约阅读时间需要 12 分钟。

给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节

点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离

，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。

每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色

。请写一个程序，快速回答这些询问。

输入

第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。

每组数据中，第一行包含两个正整数n(1<=n<=100000)和m(1<=m<=100000)，表示节点数和询问数。

第二行包含n个正整数，其中第i个数为c[i](1<=c[i]<=n)，分别表示每个节点的颜色。

第三行包含n-1个正整数，其中第i个数为f[i+1](1<=f[i]<i)，表示节点i+1的父亲节点的编号。

接下来m行，每行两个整数x(1<=x<=n)和d(0<=d<n)，依次表示每个询问。

输入数据经过了加密，对于每个询问，如果你读入了x和d，那么真实的x和d分别是x xor last和d xor last，

其中last表示这组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么last=0。

输入数据保证n和m的总和不超过500000。

输出

对于每个询问输出一行一个整数，即答案。

样例输入

5 8

1 3 3 2 2

1 1 3 3

1 0

0 0

3 0

1 3

2 1

2 0

6 2

4 1

样例输出

　　主席树神题，首先考虑没有深度限制的做法：因为每个点颜色只会对从它到根节点的链上的所有点有贡献，因此可以树上差分把这个点的权值+1，又因为同种颜色dfs序中相邻的点在它们lca到根的路径上贡献算重了，所以在LCA处权值-1。对于每次查询就变成了查询一个点的子树中的权值和，只要找出整棵树的dfs序，架在线段树上查询区间和就行了。但有了深度限制后，线段树上的子树区间需要加到答案里的点就不是连续的一段区间了。但怎么才能消除大于深度限制的点对区间和的影响？只要使他们在查询时为0就行了！那么就可以用可持久化线段树按层建树，什么意思呢？将深度为d的所有点加到第d棵可持久化线段树中，这样每次查询时，线段树中只包含d[x]层到d[x]+dep层的所有点的权值，查询的依旧是x子树区间，但d[x]+dep层以下的点这一时刻权值为0，对答案无影响。但改成按层加权值后还有一个重要的事没有解决，那就是每种颜色的dfs序的树上差分。因为是按层数加点，所以dfs序中不是按顺序加点，这里就要用到set(要是不嫌麻烦可以写treap)，对每种颜色开一个set，权值是整棵树dfs序上的顺序。每次要新加一个点时，找到这个点对应颜色的set中的前驱后继，将这两个点的lca处权值+1(在加这个点之前，它的前驱后继两个点相邻，会使lca的权值-1，这里要加回来)，再分别将这个点和它的前驱后继的lca处-1。这样就保证每一时刻一个颜色dfs序上相邻两个点的lca到根的路径上都去重了。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;int T;int n,m;int x,y;int cnt;int tot;int num;int ans;int s[100010];int t[100010];int a[100010];int d[100010];int v[100010];int to[100010];int que[100010];int ls[5000010];int rs[5000010];int next[100010];int head[100010];int sum[5000010];int root[100010];int f[100010][19];set
                
                 q[100010];set
                 
                  ::iterator it;bool cmp(int x,int y){ return d[x]
                  
                   =0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0];}void dfs(int x){ s[x]=++cnt; que[cnt]=x; for(int i=1;i<=18;i++) { f[x][i]=f[f[x][i-1]][i-1]; } for(int i=head[x];i;i=next[i]) { d[to[i]]=d[x]+1; dfs(to[i]); } t[x]=cnt;}int updata(int pre,int l,int r,int k,int v){ int rt=++cnt; if(l==r) { sum[rt]=sum[pre]+v; return rt; } ls[rt]=ls[pre]; rs[rt]=rs[pre]; sum[rt]=sum[pre]+v; int mid=(l+r)>>1; if(k<=mid) { ls[rt]=updata(ls[pre],l,mid,k,v); } else { rs[rt]=updata(rs[pre],mid+1,r,k,v); } return rt;}int query(int rt,int l,int r,int L,int R){ if(!rt||(L<=l&&r<=R)) { return sum[rt]; } int mid=(l+r)>>1; if(L>mid) { return query(rs[rt],mid+1,r,L,R); } else if(R<=mid) { return query(ls[rt],l,mid,L,R); } else { return query(ls[rt],l,mid,L,R)+query(rs[rt],mid+1,r,L,R); }}int main(){ scanf("%d",&T); while(T--) { tot=0; ans=0; cnt=0; num=0; memset(head,0,sizeof(head)); memset(root,0,sizeof(root)); memset(f,0,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); a[i]=i; q[i].clear(); } for(int i=2;i<=n;i++) { scanf("%d",&f[i][0]); add(f[i][0],i); } d[1]=1; dfs(1); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { x=y=0; it=q[v[a[i]]].lower_bound(s[a[i]]); root[d[a[i]]]=updata(root[d[a[i-1]]],1,n,s[a[i]],1); if(it!=q[v[a[i]]].end()) { y=que[(*it)]; root[d[a[i]]]=updata(root[d[a[i]]],1,n,s[lca(a[i],y)],-1); } if(it!=q[v[a[i]]].begin()) { it--; x=que[(*it)]; root[d[a[i]]]=updata(root[d[a[i]]],1,n,s[lca(a[i],x)],-1); } if(x&&y) { root[d[a[i]]]=updata(root[d[a[i]]],1,n,s[lca(x,y)],1); } q[v[a[i]]].insert(s[a[i]]); } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); x^=ans; y^=ans; ans=query(root[min(d[x]+y,d[a[n]])],1,n,s[x],t[x]); printf("%d\n",ans); } }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9449125.html

你可能感兴趣的文章