Eva

Description

n 个点 m条边的DAG，对于每个点，求它的重要度。重要度定义如下：

对于 vv这个点，将其（和其相连的所有边）删去。之后考察所有点，如果某个点初始时出度不为 0而当前出度为 0，则将这个点也删去。重复这个过程直到没有点被删去。 v 的重要度即为除它以外删掉的点的个数。

/**************************************************************

    Problem: 2815

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1088 ms

    Memory:95232 kb

****************************************************************/

 

//2815: [ZJOI2012]灾难

/*

n个生物，每个生物可以吃一些生物

灾难值指的是他挂掉以后有几种动物会挂掉

(给一个有向无环图，问每个节点删掉之后会导致多少个点不可达。)

 

显然，可以dfs拓扑排序，然后暴力搞O(n^2)

更妙的方法==》灭绝树

对于一棵多叉树的任意一个结点，当它“灭绝”时，它所有的后代也会跟着“灭绝”。

一种生物会“灭绝”只有两种情况：一是它原本就“灭绝”，二是它所有的食物都“灭绝”。

对于二

假设有生物I。很显然，只有当生物I的所有食物的最近公共祖先（LCA）J“灭绝”时，

生物I的所有食物才会同时“灭绝”（显然这里就要用到倍增求LCA的算法），

然后，我们将生物I作为生物J的一个新的孩子节点，表示当J“灭绝”时，

I也会跟着“灭绝”（因为它所有的食物都“灭绝”了）。

根据题目需求，最后只要输出每种生物在“灭绝树”中的所有后代数量

（数量的计算可以在每次“灭绝树”加入新节点时进行一次DFS）就可以了。

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int mm = 5000000+5;

const int mt = 100000+5;//我也不知到应该开多大，尽量开

vector<int>food[mt];

int to[mm<<1],nxt[mm<<1],adj[mt];

int ecnt=0;

int pnt,lst[mt],vis[mt];

int pa[mt][25],dep[mt];

void topu(int x)

{

    vis[x]=1;

    for(int i=adj[x];i;i=nxt[i])

    {

        int v=to[i];

        if(!vis[v]) topu(v);

    }

    lst[pnt--]=x;

}

void adde(int u,int v)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;

}

int sz[mt];

void dfs(int u)

{

    sz[u]=1;

    for(int i=adj[u];i;i=nxt[i])

    {

        int v=to[i];

        dfs(v),sz[u]+=sz[v];

    }

}

int llccaa(int u,int v)

{

    if(dep[u]<dep[v]) swap(u,v);

    for(int k=20;k>=0;k--)

        if(((dep[u]-dep[v])>>k)&1)

            u=pa[u][k];

    if(u==v) return u;

    for(int k=20;k>=0;k--)

        if(pa[u][k]!=pa[v][k])

            u=pa[u][k],v=pa[v][k];

    return pa[u][0];

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    int n=read();

    for(int i=1;i<=n;i++)

    {

        int x=read();

        if(x)

            for(;x;x=read())

                food[i].push_back(x),adde(x,i);

        else food[i].push_back(n+1),adde(n+1,i);

    }

    pnt=++n;

    topu(n);    

    //for(int i=1;i<=n;i++)

        //cout<<lst[i]<<endl;

    memset(to,0,sizeof(to));

    memset(adj,0,sizeof(adj));

    memset(nxt,0,sizeof(nxt));

    ecnt=0;

    dep[n]=1;

    for(int i=2;i<=n;i++)

    {

        int lca=0,u=lst[i];

        for(int v=0;v<food[u].size();v++)//u和i打反我也很难过>^<

        {

            if(lca==0) lca=food[u][v];

            else lca=llccaa(lca,food[u][v]);

        }

        adde(lca,u);

        //cout<<lca<<" "<<u<<endl;

        dep[u]=dep[lca]+1;

        pa[u][0]=lca;

        for(int k=1;k<=20;k++)

            pa[u][k]=pa[pa[u][k-1]][k-1];

    }

    dfs(n);

    for(int i=1;i<n;i++)

        printf("%d\n",sz[i]-1);

    return 0;

}