题解 CF208E 【Blood Cousins】

· · 题解

题目大意

给出一个 n 个点构成的森林，有 m 组询问
每次询问一个点 x 与多少个点拥有共同的 k 级祖先

题解

我们稍微转化一下题意：
设 y 为 x 的树上 k 级祖先，那么询问就变成了在 y 的子树中有多少个点与 y 的距离为 k。最后输出时需要减一

首先，我们dfs求出每个点的深度
然后，给每一个点 x 开一棵线段树，只需要支持单点修改和单点查询。位置 i 记录 x 子树中深度为 i 的点的出现次数
最后询问时，直接查询 y 的子树中跟 x 深度相同的节点数（记得减一）
注意要特判 x 没有 k 级祖先的情况

朴素复杂度 \operatorname{O}(n^2)
线段树合并复杂度 \operatorname{O}(n\log n)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=100000+10;
const int Maxm=5000000+10;
const int inf=0x3f3f3f3f;
int root[Maxn],head[Maxn];
int nxt[Maxn<<1],to[Maxn<<1];
int f[Maxn][23],c[Maxn];
int sum[Maxm],d[Maxn];
int ls[Maxm],rs[Maxm];
int n,m,edgecnt,idcnt,cnt;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
inline void add(int x,int y)
{
    ++edgecnt;
    nxt[edgecnt]=head[x];
    to[edgecnt]=y;
    head[x]=edgecnt;
}
inline void push_up(int x)
{
    sum[x]=sum[ls[x]]+sum[rs[x]];
}
inline void modify(int &x,int l,int r,int pos,int v)
{
    if(!x)x=++idcnt;
    if(l==r)
    {
        sum[x]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)modify(ls[x],l,mid,pos,v);
    else modify(rs[x],mid+1,r,pos,v);
    push_up(x);
}
int merge(int x,int y)
{
    if(!x || !y)return x|y;
    int cur=++idcnt;
    sum[cur]=sum[x]+sum[y];
    ls[cur]=merge(ls[x],ls[y]);
    rs[cur]=merge(rs[x],rs[y]);
    return cur;
}
int query(int x,int l,int r,int pos)
{
    if(!x)return 0;
    if(l==r)return sum[x];
    int mid=(l+r)>>1;
    if(pos<=mid)return query(ls[x],l,mid,pos);
    else return query(rs[x],mid+1,r,pos);
}
void dfs(int x,int fa)
{
    f[x][0]=fa,d[x]=d[fa]+1;
    for(int i=1;i<=17;++i)
    f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==fa)continue;
        dfs(y,x);
        root[x]=merge(root[x],root[y]);
    }
    modify(root[x],1,n,d[x],1);
}
int find(int x,int k)
{
    for(int i=17;i>=0;--i)
    if(k & (1<<i))x=f[x][i];
    return x;
}
int main()
{
//  freopen("in.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;++i)
    {
        int x=read();
        if(!x)c[++cnt]=i;
        else add(i,x),add(x,i);
    }
    for(int i=1;i<=cnt;++i)
    dfs(c[i],0);
    m=read();
    while(m--)
    {
        int x=read(),k=read();
        int pos=find(x,k);
        if(!pos)printf("0 ");
        else printf("%d ",query(root[pos],1,n,d[x])-1);
    }
    return 0;
}