BZOJ2815 [ZJOI2012]灾难

题面

http://www.lydsy.com/JudgeOnline/upload/zjoi2012.pdf

题解

​ 出题人题解:http://fanhq666.blog.163.com/blog/static/8194342620124274154996/

​ 首先,我们对整个图进行拓扑排序,得到拓扑逆序(也就是先是草之类的生产者)

​ 有一个太阳,是所有生产者的食物

​ 定义一棵灭绝树表示对于每一个节点,如果它灭绝,那么它的子树也会灭绝。

为什么是树不是图?

​ 简单yy一下:

​ 一个点有且仅有一个father,否则:A->C,B->C,也就是A灭绝,C会灭绝,B灭绝,C也会灭绝。C一定间接吃A或者吃B,所以一旦一个灭绝,它还可以吃另一个,也就是有这样一条链。

具体证明

​ 构造出这棵树就能证明了QAQ。

​ 按照拓扑序依次构建每一个生产者。

​ 对于一个生产者$i$,只有它的所有食物同时灭绝他才会灭绝。

​ 那么这个位置就是它的所有食物的LCA。

做法

​ 具体可以通过用倍增来进行动态加点和求LCA。最后$dfs$一下求子树的size-1即可

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
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<bitset>
#include<vector>
#include<set>
#include<map>
#include<ctime>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
#define pc putchar
#define RG register
char __wzp[1<<15|1],*__S=__wzp+32768;
#ifdef LOCAL
#define gc getchar
#else
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
#endif
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
const int oo = 0x3f3f3f3f,inf = oo;
#define mem(x,v) memset(x,v,sizeof(x))
#define sqr(x) ((x)*(x))
#define lowbit(x) (x&-x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define wait system("pause")
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define file(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define writeln(x) printf("%d\n",x);
#define N -1
#define M -1
struct Edge{
int to,nxt;
Edge(){}
Edge(int to,int nxt):to(to),nxt(nxt){}
}edge[2000005];
int first[100005],nume;
void Addedge(int a,int b){
edge[nume] = Edge(b,first[a]);
first[a] = nume++;
}
int deep[100005],fa[100005][20],size[100005];
int LCA(int x,int y){
if(x==-1) return y;
if(deep[x]<deep[y])swap(x,y);
for(int i=19;i>=0;i--)
if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
if(x==y)return x;
for (int i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
vector<int> G[100005];
int q[100005],front,rear,n;
int In[100005];
void Build(){
for (int i=1;i<=n;i++) G[i].clear();
for (int i=n-1;i>=0;i--){
int u = q[i],father = -1;
// printf("%d ",u);
for (int e=first[u];~e;e=edge[e].nxt)
father = LCA(father,edge[e].to);
if(father == -1) father = 0;
// printf("%d->%d\n",father,u);
G[father].pb(u);
deep[u] = deep[father] + 1;
fa[u][0] = father;
for (int j=1;(1<<j)<=deep[u];j++)
fa[u][j] = fa[fa[u][j-1]][j-1];
}
}
void get_size(int u){
size[u] = 1;
for (int i=0;i<G[u].size();i++){
get_size(G[u][i]);
size[u] += size[G[u][i]];
}
}
int main(){
n = read();
mem(In,0);
mem(first,-1);nume = 0;
for (int i=1;i<=n;i++){
int x = read();
while(x){
Addedge(i,x);
In[x]++;
x = read();
}
}
front = rear = 0;
for (int i=1;i<=n;i++) if (In[i]==0) q[rear++] = i;
while(front<rear)
for (int u=q[front++],e=first[u];~e;e=edge[e].nxt)
if(--In[edge[e].to]==0) q[rear++] = edge[e].to;
Build();
get_size(0);
for (int i=1;i<=n;i++)
printf("%d\n",size[i] - 1);
return 0;
}
/*
5
0
1 0
1 0
2 3 0
2 0
*/
文章目录
  1. 1. 题面
  2. 2. 题解
|