#477. 叶子的染色

叶子的染色

题目描述

原题来自:CQOI 2009

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

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

输入格式

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

接下来 n\red{n }行每行一个 0\red{0 }1\red{1 }的数,其中0\red{ 0 }表示黑色,1\red{1} 表示白色,依次为 c1,c2,,cn\red{c_1,c_2,\cdots ,c_n} 的值。

接下来 m1\red{m-1 }行每行两个整数 a,b\red{a,b},表示节点a\red{ a}b\red{ b} 有边相连。

输出格式

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

样例

输入样例

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

输出样例

2

提示

数据 1\red{1 } 2\red{2 } 3\red{3 } 4\red{4 } 5\red{5 } 6\red{6 } 7\red{7 } 8\red{8 } 9\red{9 } 10\red{10}
m\red{m} 10\red{10} 50\red{50} 100\red{100} 200\red{200} 400\red{400} 1000\red{1000} 4000\red{4000} 8000\red{8000} 10000\red{10000}
n\red{n} 5\red{5 } 23\red{23} 50\red{50 } 98\red{98 } 197\red{197} 498\red{498 } 2044\red{2044} 4004\red{4004} 5021\red{5021 } 4996\red{4996 }

统计

相关

在以下作业中:

DP