题目大意：
有一棵
M
M
个结点的无根树，你可以选择一个度数大于11的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 有
N
N
个叶子节点，对于每个叶结点uu，定义
c[u]
c
[
u
]
为从
u
u
到根结点的简单路径上第一个有色结点的颜色。给出每个c[u]c[u]的值，设计着色方案，使得着色结点的个数尽量少。
1<=N,M<=100000
1
<=
N
,
M
<=
100000
1<=a<b<=M
1
<=
a
<
b
<=
M
分析：
这是一道比较容易的树形dp，设
f[i][0/1/2]
f
[
i
]
[
0
/
1
/
2
]
表示给结点
i
i
涂黑色，白色，不涂色的最少着色个数。
然后易得
f[i][0]=min(f[Soni][0]−1,min(f[Soni][1],f[Soni][2]))f[i][0]=min(f[Soni][0]−1,min(f[Soni][1],f[Soni][2]))
f[i][1]=min(f[Soni][1]−1,min(f[Soni][0],f[Soni][2]))
f
[
i
]
[
1
]
=
m
i
n
(
f
[
S
o
n
i
]
[
1
]
−
1
,
m
i
n
(
f
[
S
o
n
i
]
[
0
]
,
f
[
S
o
n
i
]
[
2
]
)
)
f[i][2]=min(f[Soni][2],min(f[Soni][0],f[Soni][1]))
f
[
i
]
[
2
]
=
m
i
n
(
f
[
S
o
n
i
]
[
2
]
,
m
i
n
(
f
[
S
o
n
i
]
[
0
]
,
f
[
S
o
n
i
]
[
1
]
)
)
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100005
using namespace std;
struct Node {
int To, nxt;
}e[
2*N];
int sum[N], Ls[N], c[N] ,f[N][
3], n, m, cnt;
void dfs(
int x,
int father) {
bool flag =
1;
for (
int i = Ls[x]; i; i = e[i].nxt) {
if (e[i].To == father)
continue;
int y = e[i].To;
dfs(y, x);
flag =
0;
}
if (flag) {
f[x][c[x]] =
1;
f[x][
2] = f[x][c[x]^
1] =
2333333;
return;
}
f[x][
0] = f[x][
1] =
1;
f[x][
2] =
0;
for (
int i = Ls[x]; i; i = e[i].nxt) {
if (e[i].To == father)
continue;
int y = e[i].To;
f[x][
0] += min(f[y][
0] -
1, min(f[y][
1], f[y][
2]));
f[x][
1] += min(f[y][
1] -
1, min(f[y][
0], f[y][
2]));
f[x][
2] += min(f[y][
2], min(f[y][
0], f[y][
1]));
}
return;
}
int main() {
scanf(
"%d %d", &m, &n);
for (
int i =
1; i <= n; i++)
scanf(
"%d", &c[i]);
for (
int i =
1; i <= m -
1; i++) {
int u, v;
scanf(
"%d %d", &u, &v);
++sum[v];
e[++cnt].To = v, e[cnt].nxt = Ls[u], Ls[u] = cnt;
e[++cnt].To = u, e[cnt].nxt = Ls[v], Ls[v] = cnt;
}
int root =
0;
while (sum[root+
1] <=
1) ++root;
root +=
1;
dfs(root, -
1);
printf(
"%d\n", min(f[root][
2], min(f[root][
0], f[root][
1])));
return 0;
}
