题解：CF208E

· · 题解

CF208E 题解

这里提供一个比较劣的做法。

对于每次询问，求出 x 的 p 级表亲 t，则答案为 t 的子树内与 x 同深度的节点个数 -1。我们知道，一棵子树内的 dfs 序是连续的，考虑把询问拍成序列，用莫队处理。

时间复杂度：\Theta(m\sqrt{n})。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,K=4e2+5;
int n,fa[N],m,dp[N][20],lg[N],t,l[K],r[K],pos[N],dfn[N],siz[N],ans[N],cnt,c[N],dep[N],rnk[N];
struct ask{
    int l,r,v,id;
    bool operator<(const ask&_)const{
        return (pos[l]==pos[_.l]?(r==_.r?0:r<_.r):l<_.l);
    }
}q[N];
vector<int>v[N];
void dfs(int cur){
    dfn[cur]=++cnt,rnk[cnt]=cur,siz[cur]=1,dp[cur][0]=fa[cur],dep[cur]=dep[fa[cur]]+1;
    for(int i=1;i<=lg[dep[cur]];i++)dp[cur][i]=dp[dp[cur][i-1]][i-1];
    for(int to:v[cur])dfs(to),siz[cur]+=siz[to];
}
void add(int x){c[dep[rnk[x]]]++;}
void del(int x){c[dep[rnk[x]]]--;}
int main(){
    cin>>n;
    lg[0]=-1;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        if(fa[i])v[fa[i]].push_back(i);
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++)if(!fa[i])dfs(i);
    int t=sqrt(n);
    for(int i=1;i<=t;i++)l[i]=r[i-1]+1,r[i]=i*t;
    if(r[t]<n)t++,l[t]=r[t-1]+1,r[t]=n;
    for(int i=1;i<=t;i++)for(int j=l[i];j<=r[i];j++)pos[j]=i;
    cin>>m;
    cnt=0;
    for(int i=1;i<=m;i++){
        int x,l;
        cin>>x>>l;
        if(l>=dep[x])continue;
        cnt++;
        q[cnt].v=dep[x];
        while(l)x=dp[x][lg[l]],l-=(1<<lg[l]);
        q[cnt].l=dfn[x],q[cnt].r=dfn[x]+siz[x]-1,q[cnt].id=i;
    }
    sort(q+1,q+cnt+1);
    int l=1,r=0;
    for(int i=1;i<=cnt;i++){
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(l<q[i].l)del(l++);
        while(r>q[i].r)del(r--);
        ans[q[i].id]=c[q[i].v]-1;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
    return 0;
}