[题解]ZJOI2012灾难

发表于 | 评论数： | 阅读次数：
本文字数： 3k | 阅读时长 ≈ 3 分钟

题目描述

洛谷

题解

题目中有多个生产者，考虑建一个虚点连向所有的生产者，这样保证了图连通。显然我们要按照拓扑序处理每个节点。

一个生物死亡只有当且仅当所有指向它的生物死亡，如果它的入度为$1$比较好处理，但如果大于$1$呢？

让捕食者向被捕食者再建一条边，当遍历到一个捕食者有多条连向它的被捕食者的边时，我们可以让这个捕食者直接向它的所有被捕食者的最近公共祖先连一条边。因为它们的最近公共祖先死亡了它们会全部死亡，所以连向被捕食者的所有边与连向它们最近公共祖先的边是等价的，这样我们就保证了图成为一棵树。

如图

观察发现小强向牛和羊都有连边，牛和羊的最近公共祖先是草，这表明草死亡了牛和羊都会死亡，所以小强也会死亡。所以可以直接让小强向草连一条边。

最后只需要统计每个节点的子树大小，减去自己的$1$即可

Code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 70010;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , cnt , head[MAXN];
int deg[MAXN] , f[30][MAXN] , depth[MAXN];
int tcnt , thead[MAXN];

struct G{
	int To , Nxt;
}edge[MAXN * 100] , Tree[MAXN];

void add(int From , int To)
{
	edge[++ cnt].Nxt = head[From];
	edge[cnt].To = To;
	head[From] = cnt;
}

void addTree(int From , int To)
{
	Tree[++ tcnt].Nxt = thead[From];
	Tree[tcnt].To = To;
	thead[From] = tcnt;
}

int Lca(int x , int y)
{
	if(depth[x] < depth[y]) swap(x , y);
	for(int j = 20; j >= 0; j --) 
	  if(depth[f[j][x]] >= depth[y]) x = f[j][x];
	if(x == y) return x;
	for(int j = 20; j >= 0; j --)
	  if(f[j][x] != f[j][y]) x = f[j][x] , y = f[j][y];
	return f[0][x]; 
}

void Work(int k)
{
	for(int j = 1; j <= 20; j ++) f[j][k] = f[j - 1][f[j - 1][k]];
}

bool vis[MAXN];
int q[MAXN] , fa[MAXN];

void Toopsort()
{
	int Head = 1 , tail = 1;
	q[tail] = 0;
    depth[0] = 0;
	while(Head <= tail)
	{
		int k = q[Head];
		vis[k] = 1;
		Head ++;
		for(int i = head[k]; i != -1; i = edge[i].Nxt)
		{
			int v = edge[i].To;
			if(vis[v] or deg[v] == 0) continue;
			if(fa[v] == -1) fa[v] = k;
			else fa[v] = Lca(fa[v] , k);
			deg[v] --;
			if(deg[v] == 0) 
			{
				f[0][v] = fa[v];
				depth[v] = depth[fa[v]] + 1;
				Work(v);
				addTree(fa[v] , v);
				q[++ tail] = v;
			}
		}
	}
}

int Size[MAXN];
void Dfs(int k)
{
	Size[k] = 1;
	for(int i = thead[k]; i != -1; i = Tree[i].Nxt)
	{
		int v = Tree[i].To;
		Dfs(v);
		Size[k] += Size[v];
	}
}

int main()
{
//	freopen("catas_catas9.in" , "r" , stdin);
//	freopen("catas_catas9.out" , "w" , stdout);
	n = read();
	memset(head , -1 , sizeof(head));
	memset(fa , -1 , sizeof(fa));
	memset(thead , -1 , sizeof(thead));
	for(int i = 1; i <= n; i ++)
	{
		int x = read();
		while(x != 0)
		{
			deg[i] ++;
			add(i , x);
			add(x , i);
			x = read();
		}
		if(deg[i] == 0) deg[i] ++ , add(0 , i);
	}
	Toopsort();
	Dfs(0);
	for(int i = 1; i <= n; i ++)
	{
//		if(Size[i] == 0) cout << i << endl;
		printf("%d\n" , Size[i] - 1);
	} 
	return 0;
}