A5483. 「一本通 5.2 练习 4」叶子的染色
编程题
普及+/提高
知识点
题目描述
**原题来自：CQOI 2009**
给一棵有 $m$ 个节点的无根树，你可以选择一个度数大于 $1$ 的节点作为根，然后给一些节点（根、内部节点、叶子均可）着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点，哪怕是叶子本身。
对于每个叶子节点 $u$，定义 $c_u$ 为从根节点到 $u$ 的简单路径上最后一个有色节点的颜色。给出每个 $c_u$ 的值，设计着色方案使得着色节点的个数尽量少。
给一棵有 $m$ 个节点的无根树，你可以选择一个度数大于 $1$ 的节点作为根，然后给一些节点（根、内部节点、叶子均可）着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点，哪怕是叶子本身。
对于每个叶子节点 $u$，定义 $c_u$ 为从根节点到 $u$ 的简单路径上最后一个有色节点的颜色。给出每个 $c_u$ 的值，设计着色方案使得着色节点的个数尽量少。
输入格式
第一行包括两个数 $m,n$，依次表示节点总数和叶子个数，节点编号依次为 $1$ 至 $m$。
接下来 $n$ 行每行一个 $0$ 或 $1$ 的数，其中 $0$ 表示黑色，$1$ 表示白色，依次为 $c_1,c_2,\cdots ,c_n$ 的值。
接下来 $m-1$ 行每行两个整数 $a,b$，表示节点 $a$ 与 $b$ 有边相连。
接下来 $n$ 行每行一个 $0$ 或 $1$ 的数，其中 $0$ 表示黑色，$1$ 表示白色，依次为 $c_1,c_2,\cdots ,c_n$ 的值。
接下来 $m-1$ 行每行两个整数 $a,b$，表示节点 $a$ 与 $b$ 有边相连。
输出格式
输出仅一个数，表示着色节点数的最小值。
输入输出样例
输入 #1
5 3 0 1 0 1 4 2 5 4 5 3 5
输出 #1
2
说明/提示
| 数据 |$1$|$2$|$3$|$4$|$5$|$6$|$7$|$8$|$9$|$10$|
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| $m$ |$10$|$50$|$100$|$200$|$400$|$1000$|$4000$|$8000$|$10000$|$10000$|
| $n$ |$5$|$23$|$50$|$98$|$197$|$498$|$2044$|$4004$|$5021$|$4996$|
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| $m$ |$10$|$50$|$100$|$200$|$400$|$1000$|$4000$|$8000$|$10000$|$10000$|
| $n$ |$5$|$23$|$50$|$98$|$197$|$498$|$2044$|$4004$|$5021$|$4996$|