欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[bzoj4771] 七彩树

程序员文章站 2022-03-30 20:23:09
题意 给定一棵n个点,每个点带颜色的有根树。点的编号和颜色编号都在1到n,根的编号为1。m次询问,求x子树中与x距离边数不超过k的点中,颜色的种类数目。每个测试点有多组数据。 分析 不妨设1的父亲为0,0包含了所有颜色。不考虑深度限制,对于单独一种颜色c,易知颜色c对于任意两个色c的点之间的路径上的 ......

题意

给定一棵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("%d\n",last=query(root[min(dep[x]+k,ndp)],1,n,dfn[x],dfn[x]+siz[x]-1));
        }
    }
    return 0;
}