BZOJ 2815 [ZJOI2012]灾难

题面

题解

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
const int maxn=65534+5;
typedef long long LL;
using namespace std;
int n,fir[maxn],nxt[maxn*50],to[maxn*50],in[maxn],ecnt,sta[maxn],R[maxn],f[maxn][21],sz[maxn],l=1,r;
void add(int u,int v) {
    nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
}
int lca(int x,int y) {
    if(R[x]<R[y]) swap(x,y);
    for(int i=20;i>=0;i--) 
        if(f[x][i]!=-1&&R[f[x][i]]>=R[y])
             x=f[x][i];
    if(x==y) return y;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=-1&&f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
void tpsort() {
    for(int i=1;i<=n;++i) f[i][0]=-1;
    for(int i=1;i<=n;i++) 
        if(!in[i]) 
            sta[++r]=i,f[i][0]=0;
    while(l<=r) {
        int x=sta[l++];
        R[x]=R[f[x][0]]+1;
        for(int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];
        for(int i=fir[x];i;i=nxt[i]) {
            int y=to[i];
            in[y]--;
            if(f[y][0]==-1) f[y][0]=x;
            else f[y][0]=lca(f[y][0],x);
    
            if(!in[y]) sta[++r]=y;
        }
    }
    for(int i=r;i>=1;i--) sz[f[sta[i]][0]]+=(sz[sta[i]]+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        for(int x=1;x;) {
            scanf("%d",&x);
            if(x) { 
                in[i]++; 
                add(x,i);
            }
        }
        
    }
    tpsort();
    for(int i=1;i<=n;i++) printf("%d
",sz[i]);
    return 0;
}