【BZOJ4771】七彩树（主席树）

秒速五厘米 2021-12-01 14:24 222阅读 0赞

[点此看题面][Link 1]

**大致题意：** 一棵树中每个点有各自的颜色，强制在线询问以某个点为根的子树内深度不超过给定值的节点中有多少种本质不同的颜色。

### 主席树 ###

考虑一个子树内所有点\\(dfs\\)序是连续的，所以我们可以将其转化为序列然后用线段树维护。

又由于有深度限制，所以可以对不同深度建不同版本，使用**主席树**。

### 如何维护 ###

但是，本质不同颜色应该如何维护？

考虑对于每一种颜色，如果有两个该颜色的点同时出现，则相当于将这两个点的权值分别加\\(1\\)，而把它们\\(LCA\\)的权值减\\(1\\)。

则我们按照深度，对于每种颜色依次加入该颜色节点\\(x\\)，用\\(set\\)维护，找出其在\\(dfs\\)序中的前驱\\(pre\\)和后继\\(nxt\\)。

然后，在主席树上\\(dep\_x\\)这一版本中，将\\(x\\)这点本身权值加\\(1\\)，将\\(LCA(x,pre)\\)和\\(LCA(x,nxt)\\)两点权值减\\(1\\)，并将\\(LCA(pre,nxt)\\)这一点权值加\\(1\\)。

询问时只要求出\\(dfs\\)序中这段区间的权值和即可。

### 代码 ###

#include<bits/stdc++.h>
    #define Tp template<typename Ty>
    #define Ts template<typename Ty,typename... Ar>
    #define Reg register
    #define RI Reg int
    #define Con const
    #define CI Con int&
    #define I inline
    #define W while
    #define N 100000
    #define LN 20
    #define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
    #define swap(x,y) (x^=y^=x^=y)
    using namespace std;
    int n,d,ee,a[N+5],fa[N+5][LN+1],dep[N+5],dI[N+5],dO[N+5],D[N+5],lnk[N+5];
    struct data {int p,d;I bool operator < (Con data& o) Con {return d<o.d;}}t[N+5];
    struct edge {int to,nxt;}e[N];set<int> s[N+5];set<int>::iterator it;
    class FastIO
    {
        private:
            #define FS 100000
            #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
            #define pc(c) (C==E&&(clear(),0),*C++=c)
            #define tn (x<<3)+(x<<1)
            #define D isdigit(c=tc())
            int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
        public:
            I FastIO() {A=B=FI,C=FO,E=FO+FS;}
            Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
            Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
            Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
            I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
            #undef D
    }F;
    class ChairmanTree//主席树
    {
        private:
            #define L l,mid,O[rt].S[0]
            #define R mid+1,r,O[rt].S[1]
            #define PU(x) (O[x].V=O[O[x].S[0]].V+O[O[x].S[1]].V)
            int tot,Rt[N+5];struct node {int V,S[2];}O[N*LN<<2];
            I void ins(CI l,CI r,int& rt,RI lst,CI x,CI t)//插入
            {
                if(O[rt=++tot]=O[lst],l==r) return (void)(O[rt].V+=t);RI mid=(l+r)/2;
                x<=mid?ins(L,O[lst].S[0],x,t):ins(R,O[lst].S[1],x,t),PU(rt);
            }
            I int qry(CI l,CI r,CI rt,CI tl,CI tr)//询问
            {
                if(!rt||(tl<=l&&r<=tr)) return O[rt].V;RI mid=(l+r)/2;
                return (tl<=mid?qry(L,tl,tr):0)+(tr>mid?qry(R,tl,tr):0);
            }
        public:
            I void Clear() {tot=0,memset(Rt,0,sizeof(Rt));}//清空
            I void Insert(CI v,CI ov,CI x,CI t) {ins(1,n,Rt[v],Rt[ov],x,t);}
            I int Query(CI v,CI l,CI r) {return qry(1,n,Rt[v],l,r);}
    }C;
    I void dfs(CI x)//dfs遍历预处理LCA和dfs序
    {
        RI i;for(D[dI[x]=++d]=x,i=1;i<=LN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
        for(i=lnk[x];i;i=e[i].nxt) dfs(e[i].to);dO[x]=d;
    }
    I int LCA(RI x,RI y)//倍增求LCA
    {
        RI i;for(dep[x]<dep[y]&&swap(x,y),i=0;dep[x]^dep[y];++i) (dep[x]^dep[y])>>i&1&&(x=fa[x][i]);
        if(x==y) return x;for(i=LN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);return fa[x][0];
    }
    int main()
    {
        RI Ttot,Qtot,i,x,y,pre,nxt,ans;F.read(Ttot);W(Ttot--)
        {
            for(F.read(n),F.read(Qtot),C.Clear(),d=ee=i=0;i<=n;++i) lnk[i]=0,s[i].clear();//清空
            for(i=1;i<=n;++i) F.read(a[i]);
            for(i=2;i<=n;++i) F.read(fa[i][0]),dep[i]=dep[fa[i][0]]+1,add(fa[i][0],i);
            for(dfs(1),i=1;i<=n;++i) t[t[i].p=i].d=dep[i];sort(t+1,t+n+1);//按深度排序
            for(i=1;i<=n;++i)
            {
                C.Insert(t[i].d,t[i-1].d,dI[t[i].p],1),it=s[a[t[i].p]].lower_bound(dI[t[i].p]),pre=nxt=-1,//在该颜色对应set中找前驱后继
                it!=s[a[t[i].p]].end()&&(nxt=D[*it],C.Insert(t[i].d,t[i].d,dI[LCA(t[i].p,nxt)],-1),0),//如果存在后继，进行操作
                it!=s[a[t[i].p]].begin()&&(pre=D[*--it],C.Insert(t[i].d,t[i].d,dI[LCA(t[i].p,pre)],-1),0),//如果存在前驱，进行操作
                ~pre&&~nxt&&(C.Insert(t[i].d,t[i].d,dI[LCA(pre,nxt)],1),0),s[a[t[i].p]].insert(dI[t[i].p]);//如果同时存在前驱和后继，进行操作
            }
            ans=0;W(Qtot--) F.read(x),F.read(y),x^=ans,y^=ans,F.writeln(ans=C.Query(dep[x]+y,dI[x],dO[x]));//主席树上求和
        }return F.clear(),0;
    }

转载于:https://www.cnblogs.com/chenxiaoran666/p/BZOJ4771.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=4771