Background

.

Problem Description

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.

Input Format

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 Format

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

10 5
3 4 5 7 10
1 2
1 3
1 4
3 5
3 6
3 7
5 8
5 9
6 10

5

Hint

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