题目描述
原题来自：CQOI 2009
给一棵有
m
m 个节点的无根树，你可以选择一个度数大于
1
1 的节点作为根，然后给一些节点（根、内部节点、叶子均可）着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点，哪怕是叶子本身。
对于每个叶子节点
u
u，定义
c_u
cu
为从根节点到
u
u 的简单路径上最后一个有色节点的颜色。给出每个
c_u
cu
的值，设计着色方案使得着色节点的个数尽量少。
输入
第一行包括两个数
m,n
m,n，依次表示节点总数和叶子个数，节点编号依次为
1
1 至
m
m。
接下来
n
n 行每行一个
0
0 或
1
1 的数，其中
0
0 表示黑色，
1
1 表示白色，依次为
c_1,c_2,\cdots ,c_n
c1
,c2
,⋯,cn
的值。
接下来
m-1
m−1 行每行两个整数
a,b
a,b，表示节点
a
a 与
b
b 有边相连。
输出
输出仅一个数，表示着色节点数的最小值。
样例输入
5 3
0
1
0
1 4
2 5
4 5
3 5
样例输出
2
提示
数据范围与提示
数据 11 22 33 44 55 66 77 88 99 1010
m
m
10
10
50
50
100
100
200
200
400
400
1000
1000
4000
4000
8000
8000
10000
10000
10000
10000
n
n
5
5
23
23
50
50
98
98
197
197
498
498
2044
2044
4004
4004
5021
5021
4996
4996
来源/分类
ybttg 树形DP