P3155 [CQOI2009] Coloring the Leaves

Given an unrooted tree with $m$ nodes, you may choose any node with degree greater than $1$ as the root, and then color some nodes (the root, internal nodes, and leaves are all allowed) black or white. Your coloring must ensure that on the simple path from the root to each leaf, there is at least one colored node (possibly the leaf itself). For each leaf node $u$, define $c_u$ as the color of the last colored node on the simple path from the root to $u$. Given all values of $c_u$, design a coloring scheme that minimizes the number of colored nodes.

The first line contains two integers $m, n$, where $n$ is the number of leaves and $m$ is the total number of nodes. Nodes are numbered $1, 2, \ldots, m$, and nodes $1, 2, \ldots, n$ are leaves. Each of the next $n$ lines contains an integer $0$ or $1$ ($0$ means black, $1$ means white), in order $c_1, c_2, \ldots, c_n$. Each of the next $m-1$ lines contains two integers $a, b$, indicating that nodes $a$ and $b$ are connected by an edge.

Output a single integer: the minimum number of colored nodes.

#### Constraints For all testdata, it is guaranteed that $1 \le m \le 10^4$, $1 \le n \le 5021$, $1 \le a < b \le m$. Translated by ChatGPT 5