USACO 2018 DEC Platinum 3 -- The Cow Gathering

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

Pickupwin 冷静分析了一下，发现这是一个经典问题

题面

解

首先只考虑树形的情况，每次离开的只能是叶子节点

一个点要最后离开，拓扑关系就是一个以它为根的内向树

再加上附加边，要求不能形成环，那么对于一条附加边 (a->b) 来说，就是以 b 为根， a 子树不可选

之后的事情就很简单了

但是要注意附加边形成环的情况

Pickupwin: 懒得写拓扑判环，写了个咸鱼DFS

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
#include <cstdio>
#include <cassert>

const int MAXN=100011;

int N, M;
int C[MAXN];

struct Vert{
	int FE;
	int Dps, Dpr;
	int Dep, Pre[17];
	bool Vis, Kill;
} V[MAXN];

struct Edge{
	int y, next;
} E[MAXN<<1];

int Ecnt;

void addE(int a, int b){
	++Ecnt;
	E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;
}

int DFN;

void DFS(int at){
	V[at].Dps=++DFN;
	for(int k=V[at].FE, to;k;k=E[k].next){
		to=E[k].y;
		if(to==V[at].Pre[0])	continue;
		V[to].Dep=V[at].Dep+1;
		V[to].Pre[0]=at;
		DFS(to);
	}
	V[at].Dpr=DFN;
}

bool Win=true;

void Test(int at){
	if(V[at].Vis)	{Win=false;return;}
	V[at].Vis=true;
	for(int k=V[at].FE, to;k;k=E[k].next){
		to=E[k].y;
		if(V[to].Kill)	continue;
		Test(to);
	}
	V[at].Vis=false;
	V[at].Kill=true;
}

void Add(int l, int r, int d){
	C[l]+=d;C[r+1]-=d;
}

void Add(){
	++C[0];
}

int Jump(int p, int a){
	for(int i=16;i>=0;--i)
		if(V[V[p].Pre[i]].Dep>V[a].Dep)
			p=V[p].Pre[i];
	return p;
}

inline bool In(const int &f, const int &a){
	return V[f].Dps<=V[a].Dps && V[f].Dpr>=V[a].Dpr;
}

void Deal(int r, int a){
	if(!In(a, r))	Add(V[a].Dps, V[a].Dpr, 1);
	else{
		int p=Jump(r, a);
		Add();Add(V[p].Dps, V[p].Dpr, -1);
	}
}

void Show(bool i){
	i|=!Win;
	printf("%d\n", !i);
}

int main(){
	
	freopen("gathering.in", "r", stdin);
	freopen("gathering.out", "w", stdout);
	
	scanf("%d%d", &N, &M);
	
	for(int i=1, a, b;i<N;++i){
		scanf("%d%d", &a, &b);
		addE(a, b);addE(b, a);
	}
	
	V[1].Dep=1;
	DFS(1);
	assert(DFN==N);
	
	for(int j=1;j<17;++j)
		for(int i=1;i<=N;++i)
			V[i].Pre[j]=V[V[i].Pre[j-1]].Pre[j-1];
	
	Ecnt=0;
	for(int i=1;i<=N;++i)	V[i].FE=0;
	
	for(int i=1, a, b;i<=M;++i){
		scanf("%d%d", &a, &b);
		Deal(b, a);addE(a, b);
	}
	
	for(int i=1;i<=N && Win;++i)	if(!V[i].Kill)	{Test(i);}
	
	for(int i=1;i<=N;++i)	C[i]+=C[i-1];
	
	for(int i=1;i<=N;++i)
		Show(C[V[i].Dps]>0);
	
	return 0;
}