题解P2892 追捕盗贼

本篇题解讲述的为非完美做法,但是可以骗到96分

说实话我在网上找了好久结果都是这个O(n2)O(n^2)的非正解树型DPDP

听说有个O(N)O(N)​的正解在某篇论文里?

算了反正我也看不懂

所以我接下来就介绍一下这个O(n2)O(n^2)的树型DPDP吧QwQ

顺手丢一下我学习的这篇blog​

预处理

首先我们先用f[i]f[i]表示占领以ii为根的子树所需要的人数

然后我们可以很显然地列出一个方程f[u]=max{f[v]}f[u] = \max\{f[v]\}

然后我们还要特判一下,如果有多个f[v]=max{f[v]}f[v] = max\{f[v]\},那么得f[u]f[u]得再加上1

因为在我们进行每一个子树的占领的时候除了最后一个,必须得有一个人待在root处(具体可以看后面的代码)

构造方案

首先,我们预处理nn次,分别以1~n为根,接下来就可以确定一个答案最小的根。

确认根之后,我们显然要先向根丢一个人,然后以为前面所说,我们得先把f[v]f[v]不是最大的vv给先处理掉,然后再做f[v]f[v]最大的vv

而我们访问一棵子树的顺序如下:

  • uu节点放一个警探
  • uu节点的其中一个警探走向vv节点(为了防止目标待在uvu \rightarrow v的边上赖着不走)
  • 递归做vv节点

代码

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<bits/stdc++.h>

#define ll long long
#define INF 2147483647

inline int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

int head[100010];
int nxt[20010];
int end[20010];
char type[100000];
int num1[100000], num2[100000];
int cnt = 0;
int cou = 0;
int f[20010];

void link(int a, int b){
nxt[++cou] = head[a];
head[a] = cou;
end[cou] = b;
}

void dfs(int cur, int last){
int max = 0;
bool mt = true;
for(int x = head[cur]; x != -1; x = nxt[x]){
if(end[x] != last){
dfs(end[x], cur);
if(f[end[x]] > max){
max = f[end[x]];
mt = false;
} else if(f[end[x]] == max)
mt = true;
}
}
if(mt)
f[cur] = max + 1;
else
f[cur] = max;
}

void dfs2(int cur, int last){
int max = 0;
bool mt = true;
int degree = 0;
int pos;
for(int x = head[cur]; x != -1; x = nxt[x]){
if(end[x] != last){
dfs(end[x], cur);
if(f[end[x]] > max){
max = f[end[x]];
mt = false;
pos = end[x];
} else if(f[end[x]] == max)
mt = true;
degree++;
}
}
// printf("%d %d pos = %d\n", cur, last, pos);
if(degree == 0){
type[++cnt] = 'B';
num1[cnt] = cur;
return ;
}
for(int x = head[cur]; x != -1; x = nxt[x]){
if(end[x] != pos && end[x] != last){
type[++cnt] = 'L';
num1[cnt] = cur;
type[++cnt] = 'M';
num1[cnt] = cur;
num2[cnt] = end[x];
dfs2(end[x], cur);
}
}
type[++cnt] = 'M';
num1[cnt] = cur;
num2[cnt] = pos;
dfs2(pos, cur);
if(mt)
f[cur] = max + 1;
else
f[cur] = max;
}

int main(){
memset(head, -1, sizeof(head));
int n = inp();
for(int i = 1; i < n; i++){
int u = inp();
int v = inp();
link(u, v);
link(v, u);
}
int root = 0;
int min = INF;
for(int i = 1; i <= n; i++){
dfs(i, 0);
if(f[i] < min){
min = f[i];
root = i;
}
}
dfs2(root, 0);
printf("%d\n%d\n", min, cnt + 1);
printf("L %d\n", root);
for(int i = 1; i <= cnt; i++){
putchar(type[i]);
printf(" %d", num1[i]);
if(type[i] == 'M')
printf(" %d", num2[i]);
putchar('\n');
}
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。