P2597 [ZJOI2012]灾难

题意

这题思路好奇怪啊

见到有向无环图显然是要拓朴排序,不妨按照被吃向吃连边,那么\(x\)灭绝当且仅当x的入点都灭绝,于是考虑怎样x的入点都灭绝

比如4号节点,它灭绝当且仅当2和3灭绝,2和3灭绝当且仅当1灭绝,我们发现1是2和3的lca

于是得出这样一个做法:将每个点\(x\)和灭绝后能灭绝\(x\)的点\(y\)连边\((y->x)\),y是所有x的父亲的lca,这样显然是棵树,每个点的灾难度即子树大小减一

建树可以边拓朴排序边维护倍增数组,可以见代码

code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=70010;
const int maxm=2000010;
const int inf=0x3f3f3f3f;
int n,cnt1,cnt2,cnt,t;
int head1[maxn],head2[maxn],head[maxn],deg[maxn],dep[maxn],size[maxn];
int f[maxn][20];
struct edge{int to,nxt;}e[maxm],e1[maxm],e2[maxm];
inline void add1(int u,int v){e1[++cnt1].nxt=head1[u];head1[u]=cnt1;e1[cnt1].to=v;}
inline void add2(int u,int v){e2[++cnt2].nxt=head2[u];head2[u]=cnt2;e2[cnt2].to=v;}
inline void add(int u,int v){e[++cnt].nxt=head[u];head[u]=cnt;e[cnt].to=v;}
inline int lca(int x,int y)
{
    if(dep[x]>dep[y])swap(x,y);
    for(int i=t;~i;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];
    if(x==y)return x;
    for(int i=t;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++)if(!deg[i])add1(n+1,i),add2(i,n+1),deg[i]++;
    q.push(n+1);dep[n+1]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head1[x];i;i=e1[i].nxt)
        {
            int y=e1[i].to;deg[y]--;
            if(!deg[y])
            {
                int z=0;
                for(int j=head2[y];j;j=e2[j].nxt)
                    if(!z)z=e2[j].to;
                    else z=lca(z,e2[j].to);
                add(z,y);f[y][0]=z;dep[y]=dep[z]+1;
                for(int j=1;j<=t;j++)f[y][j]=f[f[y][j-1]][j-1];
                q.push(y);
            }
        }
    }
}
void dfs(int x)
{
    size[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        dfs(y);size[x]+=size[y];
    }
}
int main()
{
    scanf("%d",&n);t=(int)log2(n)+1;
    for(int i=1;i<=n;i++)
    {
        int x;
        while(~scanf("%d",&x)&&x)add1(x,i),add2(i,x),deg[i]++;
    }
    topsort();
    /*for(int x=1;x<=n+1;x++)
    {
        printf("now::%d\n",x);
        for(int i=head[x];i;i=e[i].nxt)printf("%d ",e[i].to);
        puts("");
    }*/
    dfs(n+1);
    for(int i=1;i<=n;i++)printf("%d\n",size[i]-1);
    return 0;
}