BZOJ 4771: 七彩树 可持久化线段树+树链的并

这个思路挺有意思的 ~

利用树链的并来保证每个颜色只贡献一次，然后用可持久化线段树维护

code:

#include <set>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100005

#define setIO(s) freopen(s".in","r",stdin)  , freopen(s".out","w",stdout)

using namespace std;

namespace seg

{

    #define lson t[x].ls

    #define rson t[x].rs

    int tot;

    struct node

    {

        int ls,rs,sum;

    }t[N*80];

    void clr()

    {

        for(int i=1;i<=tot;++i) t[i].ls=t[i].rs=t[i].sum=0;

        tot=0;

    }

    int newnode()

    {

        return ++tot;

    }

    void build(int &x,int l,int r)

    {

        x=newnode();

        if(l==r)   return;

        int mid=(l+r)>>1;

        if(l<=mid) build(lson,l,mid);

        if(r>mid)  build(rson,mid+1,r);

    }

    int cop(int x,int l,int r,int p,int v)

    {

        int now=newnode();

        t[now]=t[x];

        t[now].sum+=v;

        if(l==r) return now;

        int mid=(l+r)>>1;

        if(p<=mid) t[now].ls=cop(lson,l,mid,p,v);

        else t[now].rs=cop(rson,mid+1,r,p,v);

        return now;

    }

    int query(int x,int l,int r,int L,int R)

    {

        if(!x) return 0;

        if(l>=L&&r<=R) return t[x].sum;

        int re=0;

        int mid=(l+r)>>1;

        if(L<=mid) re+=query(lson,l,mid,L,R);

        if(R>mid)  re+=query(rson,mid+1,r,L,R);

        return re;

    }

    #undef lson

    #undef rson

};

set<int>se[N];

set<int>::iterator fr,ba;

int edges,n,m,tim,ct;

int hd[N],to[N],nex[N],col[N],nod[N],st[N],ed[N];

int fa[N],dfn[N],dep[N],size[N],son[N],top[N];

int id[N],rt[N];

bool cmp(int a,int b)

{

    return dep[a]<dep[b];

}

void add(int u,int v)

{

    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;

}

void dfs1(int u,int ff)

{

    size[u]=1;

    dfn[u]=++tim;

    st[u]=dfn[u];

    nod[dfn[u]]=u;

    dep[u]=dep[ff]+1;

    for(int i=hd[u];i;i=nex[i])

    {

        int v=to[i];

        dfs1(v,u);

        size[u]+=size[v];

        if(size[v]>size[son[u]])  son[u]=v;

    }

    ed[u]=tim;

}

void dfs2(int u,int tp)

{

    top[u]=tp;

    if(son[u])   dfs2(son[u],tp);

    for(int i=hd[u];i;i=nex[i])

    {

        if(to[i]!=son[u])

        {

            dfs2(to[i],to[i]);

        }

    }

}

int LCA(int x,int y)

{

    while(top[x]!=top[y])

    {

        dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];

    }

    return dep[x]<dep[y]?x:y;

}

void solve()

{

    int i,j,last=0;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i)  scanf("%d",&col[i]);

    for(i=2;i<=n;++i)

    {

        scanf("%d",&fa[i]);

        add(fa[i],i);

    }

    dfs1(1,0);

    dfs2(1,1);

    for(i=1;i<=n;++i)   id[i]=i;

    sort(id+1,id+1+n,cmp);

    int lst=0;

    seg::build(rt[0],1,n);

    for(i=1;i<=n;++i)

    {

        int p=id[i];

        int c=col[p];

        while(dep[p]>lst)  rt[lst+1]=rt[lst],++lst;

        se[c].insert(dfn[p]);

        fr=ba=se[c].lower_bound(dfn[p]),ba++;

        if(fr!=se[c].begin())

        {

            --fr;

            rt[lst]=seg::cop(rt[lst],1,n,dfn[LCA(nod[*fr],p)],-1);

            ++fr;

        }

        if(ba!=se[c].end())

        {

            rt[lst]=seg::cop(rt[lst],1,n,dfn[LCA(nod[*ba],p)],-1);

        }

        if(fr!=se[c].begin()&&ba!=se[c].end())

        {

            --fr;

            rt[lst]=seg::cop(rt[lst],1,n,dfn[LCA(nod[*fr],nod[*ba])],1);

        }

        rt[lst]=seg::cop(rt[lst],1,n,dfn[p],1);

    }

    for(i=1;i<=m;++i)

    {

        int x,d;

        scanf("%d%d",&x,&d);

        x^=last,d^=last;

        last=seg::query(rt[min(n,dep[x]+d)],1,n,st[x],ed[x]);

        printf("%d\n",last);

    }

    for(i=1;i<=n;++i)  son[i]=0;

    for(i=1;i<=n;++i)  hd[i]=0;

    for(i=1;i<=edges;++i) nex[i]=to[i]=0;

    edges=tim=0;

    seg::clr();

    for(i=1;i<=n;++i)  se[i].clear();

}

int main()

{

    // setIO("input");

    int i,j,T;

    scanf("%d",&T);

    while(T--)  solve();

    return 0;

}