4290 - 树形动态:叶子的染色

给一棵有 m 个节点的无根树,你可以选择一个度数大于 1 的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。

对于每个叶子节点 u,定义 cu 为从根节点到 u 的简单路径上最后一个有色节点的颜色。给出每个 cu  的值,设计着色方案使得着色节点的个数尽量少。

输入

第一行包括两个数 m,n,依次表示节点总数和叶子个数,节点编号依次为 1 至 m。

接下来 n 行每行一个 0 或 1 的数,其中 0 表示黑色,1 表示白色,依次为 c1,c2,⋯,cn  的值。

接下来 m−1 行每行两个整数 a,b,表示节点 a 与 b 有边相连。

输出

输出仅一个数,表示着色节点数的最小值。

样例

输入

5 3
0
1
0
1 4
2 5
4 5
3 5

输出

2

提示

数据范围与提示:

数据12345678910
m10       50      100      200       400     1000      4000      8000     10000      10000    
n52350981974982044400450214996

 

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题