叶子的染色(Coloring Leaves)

题目描述

给一棵 $m$ 个结点的无根树，你可以选择一个度数大于 $1$ 的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。

你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。

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

输入格式

第一行包含两个整数 $m,n$，其中 $n$ 是叶子的个数，$m$ 是结点总数。结点编号为 $1,2,\ldots,m$，其中编号 $1,2,\ldots ,n$ 是叶子。

以下 $n$ 行每行一个 $0$ 或 $1$ 的整数（$0$ 表示黑色，$1$ 表示白色），依次为 $c_1,c_2,\ldots,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\le m\le 10^4$，$1\le n\le 5021$，$1\le a < b \le m$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接