好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：CQOI 2009

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

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

---

输入格式

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

接下来 $n$ 行每行一个 $0$ 或 $1$ 的数，其中 $0$ 表示黑色，$1$ 表示白色，依次为 $c_1, c_2, \dots, c_n$ 的值（按叶子编号顺序给出，叶子编号在输入中隐含？需注意：题目中叶子编号依次为 $1$ 到 $n$ 吗？看样例，$m=5,n=3$，叶子编号是 1,2,3）。

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

---

输出格式

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

---

样例

样例输入

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

样例输出

2

样例解释

$m=5, n=3$，叶子编号 1,2,3，对应 $c$ 值分别为 0,1,0。

树边：

• 1-4
• 2-5
• 4-5
• 3-5

树结构：

    5
   /|\
  2 3 4
       \
        1

叶子是 1,2,3。

选择根节点：度数大于 1 的节点有 4 和 5。选择 5 为根。

目标：对每个叶子 $u$，从根到 $u$ 的路径上最后一个有色节点颜色为 $c_u$。

一种方案：

• 将节点 5 着黑色（颜色 0）
• 将节点 4 着白色（颜色 1）

检查：

• 叶子 1：路径 5-4-1，最后一个有色节点是 4（白色），$c_1=0$ 不符合？等一下，$c_1=0$ 要求黑色。
  那么调整：节点 5 着黑色（0），节点 4 也着黑色（0）。
  叶子 1：路径 5-4-1，最后一个有色节点是 4（黑色），$c_1=0$ 符合。
  叶子 2：路径 5-2，最后一个有色节点是 5（黑色），$c_2=1$ 要求白色，不符合。
  因此需要在节点 2 处着色白色（1），这样路径 5-2 最后一个有色节点是 2（白色），符合 $c_2=1$。
  叶子 3：路径 5-3，最后一个有色节点是 5（黑色），$c_3=0$ 符合。
  着色节点：5(0), 4(0), 2(1)，共 3 个节点。

能否更优？
如果根选 4：树结构以 4 为根：

    4
   / \
  1   5
     /|\
    2 3 ?

这样可能更好吗？
我们试根为 4：

• 着色节点 4 为黑色（0）
  叶子 1：路径 4-1，最后有色节点 4（黑），$c_1=0$ 符合
  叶子 2：路径 4-5-2，需要最后一个有色节点为白色（$c_2=1$），可以在 5 或 2 着色白色，但 5 会影响叶子 3。
  如果 5 着白色，叶子 3 路径 4-5-3，最后有色节点 5（白），$c_3=0$ 不符合，所以必须在 2 着色白色。
  叶子 3：路径 4-5-3，最后有色节点？如果没有在 5 着色，则最后有色节点是 4（黑），$c_3=0$ 符合。
  所以着色节点：4(黑), 2(白)，共 2 个节点，比根为 5 更优。

因此最小着色节点数为 2。

---

数据范围

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

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 树形 DP，状态设计需考虑颜色需求。

由于根可以任意选择（度数大于1），但可以证明：最优解中，根选任意一个度数大于1的节点均可得到相同的最优值，因此可以随便选一个非叶子节点作为根（比如选节点 $n+1$ 如果编号连续的话，但这里我们选第一个度数大于1的节点）。

设 $dp[u][0]$ 表示将 $u$ 着黑色（0）时，以 $u$ 为根的子树中需要着色的最少节点数；
$dp[u][1]$ 表示将 $u$ 着白色（1）时的最少着色节点数；
$dp[u][2]$ 表示 $u$ 不着色时的最少着色节点数。

转移：

• 如果 $u$ 是叶子（度数为1）：根据 $c_u$ 确定可行状态：
  • 若 $c_u=0$，则 $dp[u][0]=1$（自己着色黑），$dp[u][1]=\infty$（不能着白），$dp[u][2]=\infty$（不能不着色，因为路径最后一个有色节点是自己，必须着色且颜色正确）
  • 若 $c_u=1$，则 $dp[u][1]=1$，$dp[u][0]=\infty$，$dp[u][2]=\infty$
• 如果 $u$ 不是叶子： 对每个子节点 $v$，$u$ 的状态会影响 $v$ 的需求：
  • 若 $u$ 着色黑（0），则对于 $v$，从 $u$ 到 $v$ 的路径上最后一个有色节点已经是黑色，所以 $v$ 可以继承 $u$ 的颜色（即 $v$ 可以不着色），也可以自己着色任意颜色。
    所以 $dp[u][0] = 1 + \sum_{v} \min(dp[v][0], dp[v][1], dp[v][2])$
  • 若 $u$ 着色白（1），类似：
    $dp[u][1] = 1 + \sum_{v} \min(dp[v][0], dp[v][1], dp[v][2])$
  • 若 $u$ 不着色，则对于 $v$，从 $u$ 到 $v$ 的路径上最后一个有色节点还没出现，所以 $v$ 必须自己解决颜色需求，即 $v$ 必须着色，且颜色必须为 $c_v$（对叶子而言）或适应子树需求。
    所以 $dp[u][2] = \sum_{v} \min(dp[v][0], dp[v][1])$

最后答案为 $\min(dp[root][0], dp[root][1], dp[root][2])$。

复杂度 $O(m)$。