原题来自:CQOI 2009
给一棵有 m 个节点的无根树,你可以选择一个度数大于 1的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。
m
1
对于每个叶子节点 u,定义 c_u 为从根节点到 u的简单路径上最后一个有色节点的颜色。给出每个 c_u 的值,设计着色方案使得着色节点的个数尽量少。
u
第一行包括两个数m,n,依次表示节点总数和叶子个数,节点编号依次为 1 至 m。
m,n
接下来n 行每行一个 0 或1 的数,其中0表示黑色,1表示白色,依次为 c_1,c_2,⋯,c_n 的值。
n
0
接下来 m−1行每行两个整数a,b,表示节点 a 与b有边相连。
m−1
a,b
a
b
输出仅一个数,表示着色节点数的最小值。
5 30101 42 54 53 5
2
数据范围与提示: