[ZJOI2012]灾难

Posted on | In

$ZJOI$里面的小清新思维题，思路参考了一些大神的博客

首先每个节点死亡的条件就是指向它的所有食物都已经死亡

那么我们可以反向建图，每个点指向它的食物

既然保证这个图没有环，那么我们显然可以拓扑排序

然后我们继续思考，不难发现每个节点死亡的条件等价于它所有食物的$LCA$死亡

因为它所有食物的$LCA$已经死亡，所以它的所有食物也都会死亡

最后求一下所有子树大小的前缀和就行，这里记得要减去自身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
int m,n,sum,num1,num2;
int to1[400004],to2[400004];
int from1[400004],from2[400004];
int head1[400004],head2[400004];
int ans[100001],ind[100001],topo[100001];
int f[100001][18],depth[100001],father[100001];
inline void add1(int from,int to) {
    from1[++num1]=head1[from];
    to1[num1]=to;
    head1[from]=num1;
}
inline void add2(int from,int to) {
    from2[++num2]=head2[from];
    to2[num2]=to;
    head2[from]=num2;
}
inline int LCA(int x,int y) {
    if(depth[x]<depth[y]) swap(x,y);
    for(register int i=16;i>=0;--i)
        if(f[x][i]!=0&&depth[f[x][i]]>=depth[y]) x=f[x][i];
    if(x==y) return y;
    for(register int i=16;i>=0;--i)
        if(f[x][i]!=0&&f[y][i]!=0&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return father[x];
}
inline void RMQ(int x) {
    f[x][0]=father[x];
    for(register int i=1;i<=16;++i) f[x][i]=f[f[x][i-1]][i-1];
}
inline void Build() {
    depth[n+1]=1,father[n+1]=n+1;
    for(register int i=n;i;--i) {
        int x=topo[i];
        if(!head1[x]) {
            add2(n+1,x),depth[x]=2;
            f[x][0]=n+1,father[x]=n+1;
            continue ;
        }
        int lca=to1[head1[x]];
        for(register int i=from1[head1[x]];i;i=from1[i]) lca=LCA(lca,to1[i]);
        depth[x]=depth[lca]+1,father[x]=lca;
        add2(lca,x),RMQ(x);
    }
}
inline void DPtree(int x) {
    ans[x]=1;
    for(register int i=head2[x];i;i=from2[i])
        DPtree(to2[i]),ans[x]+=ans[to2[i]];
}
inline void Toposort() {
    queue < int > Q;
    for(register int i=1;i<=n;++i)
        if(!ind[i]) Q.push(i);
    while(!Q.empty())  {
        int x=Q.front();
        Q.pop(); topo[++sum]=x;
        for(register int i=head1[x];i;i=from1[i]) {
            --ind[to1[i]];
            if(!ind[to1[i]]) Q.push(to1[i]);
        }
    }
}
int main() {
    scanf("%d",&n);
    for(register int i=1;i<=n;++i) {
        while(true) {
            scanf("%d",&m);
            if(!m) break ;
            else add1(i,m),++ind[m];
        }
    }
    Toposort(); Build(); DPtree(n+1);
    for(register int i=1;i<=n;++i) printf("%d\n",ans[i]-1);
    return 0;
}