Bzoj 1304(树形DP)

BZOJ 1304
题意:见上。

显然随意找一个不是叶子的点当根即可。
设$dp(u, 0/1/2)$为$u$点填$0,1$色,不填($2$)的满足最小值。
然后转移即可。具体看代码。

怎么那么水的 DP 我没想出来……

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 10000 + 5, ZINF = 2000000000;
struct edge {int v, nxt; } ed[MAXN * 2];
int m, n, c[MAXN], dp[MAXN][3], en, hd[MAXN];
void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}
void dfs(int u, int fa) {
if (u <= n) {
dp[u][c[u]] = 1, dp[u][2] = dp[u][c[u] ^ 1] = ZINF;
return ;
} else dp[u][1] = 1, dp[u][0] = 1, dp[u][2] = 0;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
dfs(e.v, u);
dp[u][0] += min(dp[e.v][0] - 1, dp[e.v][1]);
dp[u][1] += min(dp[e.v][1] - 1, dp[e.v][0]);
dp[u][2] += min(min(dp[e.v][0], dp[e.v][1]), dp[e.v][2]);
}
}
}
void clean() {
en = 0, ms(hd, -1);
}
int solve() {
scanf("%d%d", &m, &n);
if (m == 1) return printf("1\n"), 0;
for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
clean();
for (int u, v, i = 1; i < m; ++i) scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
dfs(n + 1, 0);
//cerr << "???" << dp[n + 1][0] << " " << dp[n + 1][1] << " " << dp[n + 1][2] << endl;
printf("%d\n", min(min(dp[n + 1][0], dp[n + 1][1]), dp[n + 1][2]));
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------