#T1583. 「一本通 5.2 练习 4」叶子的染色

    ID: 2513 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>树形 DPCQOI早于 2010price::50source::ybttk

「一本通 5.2 练习 4」叶子的染色

题目描述

原题来自:CQOI 2009

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

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

输入格式

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

接下来 nn 行每行一个 0011 的数,其中 00 表示黑色,11 表示白色,依次为 c1,c2,,cnc_1,c_2,\cdots ,c_n 的值。

接下来 m1m-1 行每行两个整数 a,ba,b,表示节点 aabb 有边相连。

输出格式

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

样例

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

数据范围与提示

数据 11 22 33 44 55 66 77 88 99 1010
mm 1010 5050 100100 200200 400400 10001000 40004000 80008000 1000010000
nn 55 2323 5050 9898 197197 498498 20442044 40044004 50215021 49964996