P16294 [Lanqiao Cup 2026 NOI Qualifier Java Group A] Subtree Coloring

.

Given a tree with $n$ nodes, the nodes are numbered from $1$ to $n$, where node $1$ is the root. Now you need to choose some nodes in this tree to color. There are $m$ key nodes in the tree. For each key node $x$, let the size of its subtree be $s$ (the subtree includes $x$ itself and all of its descendants). Then, in the subtree rooted at $x$, the number of colored nodes must be at least $\lceil \frac{s}{2} \rceil$. Please find the minimum number of nodes that need to be colored while satisfying the requirements of all key nodes.

The input has a total of $n + 1$ lines. The first line contains two integers $n, m$, representing the total number of nodes and the number of key nodes. The second line contains $m$ distinct integers, representing the indices of all key nodes. In the next $n - 1$ lines, each line contains two integers $a, b$, indicating that there is an edge between node $a$ and node $b$.

Output one integer, representing the minimum total number of nodes that need to be colored.

### Sample Explanation One optimal solution is to color nodes $4, 5, 7, 9, 10$, for a total of $5$ nodes. ### Constraints For $30\%$ of the testdata, $1 \le n \le 200$. For all testdata, $1 \le m \le n \le 100000$, and $1 \le a, b \le n$. Translated by ChatGPT 5