[ZJOI]2012灾难

Description

阿米巴是小强的好朋友。 阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝 了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引 发一系列的生态灾难。 学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂 蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发 重大的灾难。 我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的 有向图来描述生物之间的关系：一个食物网有 n 个点，代表 n 种生物，如 果生物 x 可以吃生物 y，那么从 y 向 x 连一个有向边。这个图没有环。 图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光 合作用来生存；而有连出边的点代表的都是消费者，它们必须通过吃其他生 物来生存。如果某个消费者的所有食物都灭绝了，它会跟着灭绝。 我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么 会跟着一起灭绝的生物的种数。 给定一个食物网，你要求出每个生物的灾难值

首先进行拓扑，把每个人的食物和自己的顺序找出来，然后建一个灾难树，每个节点要连的点为该节点所有的食物在灾难树上的lca。动态维护倍增lca。把食物向吃的人连边。
再树形DP求子树大小就好了。
借鉴黄学长的神奇lca%%%

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 76000
#define M 2001000
using namespace std;
int n,head[N],to[M],nxt[M],cnt;
int rd[N];int bin[30],tur[N],tot1,f[N];
queue<int> q;
bool inq[N];
int headt[N],tot[M],nxtt[M],cntt,deep[N],fa[N][30],ans[N];
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
void addt(int x,int y)
{
    int i;
    if(x==-1) x=0;
    tot[++cntt]=y;
    nxtt[cntt]=headt[x];
    headt[x]=cntt;
    deep[y]=deep[x]+1;
    fa[y][0]=x;
    for(i=1;i<=19;i++)
        fa[y][i]=fa[fa[y][i-1]][i-1];
}
void bin_ready()
{
    int i; bin[0]=1;
    for(i=1;i<=19;i++)
        bin[i]=bin[i-1]<<1;
}
int lca(int x,int y)
{
    int i;
    if(deep[x]<deep[y]) swap(x,y);
    int t=deep[x]-deep[y];
    for(i=0;bin[i]<=t;i++)
        if(t&bin[i]) x=fa[x][i];
    if(x==y) return x;
    for(i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void topsort()
{
    bin_ready();
    int i,t,j,y,x;
    for(i=1;i<=n;i++)
        if(rd[i]==0) q.push(i);
    while(q.size())
    {
        t=q.front(),q.pop();
        tur[++tot1]=t;
        for(j=head[t];j;j=nxt[j])
        {y=to[j];
            rd[y]--;
            if(rd[y]==0) q.push(y);
        }
    }
    for(i=1;i<=tot1;i++)
    {
        y=tur[i];
        addt(f[y],y);
        for(j=head[y];j;j=nxt[j])
        {
            x=to[j];
            if(f[x]==-1) f[x]=y;
            else f[x]=lca(f[x],y);
        }
    }
}
void dfs(int x)
{
    int i;
    for(i=headt[x];i;i=nxtt[i])
    {
        dfs(tot[i]);
        ans[x]+=(ans[tot[i]]+1);
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    scanf("%d",&n);
    int j,i,x;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        while(x!=0)
        {
            add(x,i),rd[i]++;
            scanf("%d",&x);
        }
    }
    topsort();
    //for(i=1;i<=tot1;i++) printf("%d ",tur[i]);
    dfs(0);
    for(i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}
/*5
0
1 0 1 0 2 3 0 2 0*/