代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
#define int long long
int n,head[maxn],rd[maxn],dep[maxn],cnt,top[maxn],tot,fa[maxn],f[maxn][25],Size[maxn],root;
struct E{
    int to,next;
}edge[maxn<<1];
vector<int>food[maxn];
vector<int>g[maxn];
inline void add(int u,int v){
    edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}
void topo(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();q.pop();
        top[++tot]=x;
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].to;rd[y]--;
            if(!rd[y])q.push(y);
        }
    }
    return;
}
int lca(int x,int y){
    if(dep[x]>dep[y])swap(x,y);
    if(dep[y]>dep[x]){
        for(int i=20;i>=0;i--){
            if(dep[y]>=dep[x]&&f[y][i])y=f[y][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]&&f[x][i]&&f[y][i])x=f[x][i],y=f[y][i];
    }
    return fa[x];
}
void init(int x){
    dep[x]=dep[fa[x]]+1;f[x][0]=fa[x];
    for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
    return;
}
void dfs(int x){
    Size[x]=1;
    for(int i=0;i<g[x].size();i++){
        dfs(g[x][i]);
        Size[x]+=Size[g[x][i]];
    }
    return;
}
signed main(){
    memset(fa,-1,sizeof(fa));
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%lld",&x);
        while(x!=0){
            add(x,i);rd[i]++;
            food[i].push_back(x);
            scanf("%lld",&x);
        }
    }
    for(int i=1;i<=n;i++)if(!rd[i])add(0,i),food[i].push_back(0),rd[i]++;
    topo();
    for(int i=2;i<=tot;i++){
        int x=top[i];
        int LCA=food[x][0];
        for(int j=1;j<food[x].size();j++){
            LCA=lca(LCA,food[x][j]);
        }
        g[LCA].push_back(x);
        fa[x]=LCA;init(x);
    }
    dfs(root);
    for(int i=1;i<=n;i++)printf("%lld\n",Size[i]-1);
    return 0;
}