P8428 [COI 2020] Pastiri

Given a tree with $N$ nodes labeled from $1$ to $N$, there are sheep on $K$ nodes. Your task is to place some shepherds on the tree. These shepherds are lazy: each shepherd will only watch the sheep that are closest to them. Of course, if there are multiple closest sheep, the shepherd will watch all of them. A shepherd may be placed on the same node as a sheep, but in that case, the shepherd will only watch the sheep on that node. Find a placement of shepherds that minimizes the total number of shepherds.

The first line contains two integers $N, K$, representing the number of nodes in the tree and the number of nodes with sheep. The next $N - 1$ lines each contain two integers $a_i, b_i$, representing an edge of the tree. The $(N + 1)$-th line contains $K$ integers $o_i$, representing the labels of the nodes that have sheep.

The first line contains an integer $X$, the minimum total number of shepherds. The second line contains $X$ integers, indicating the node where each shepherd is placed. If there are multiple solutions, output any one of them.

#### Explanation for Sample 3  #### Constraints **This problem uses bundled testdata.** - Subtask 1 (8 pts): $1 \le N \le 5 \times 10^5$, and every node $i$ is connected to $i + 1$ ($1 \le i \le N - 1$). - Subtask 2 (18 pts): $1 \le K \le 15$, $1 \le N \le 5 \times 10^5$. - Subtask 3 (23 pts): $1 \le N \le 2000$. - Subtask 4 (51 pts): $1 \le N \le 5 \times 10^5$. For $100\%$ of the data: $1 \le K \le N$, $1 \le a_i, b_i \le N$, $1 \le o_i \le N$. **This problem uses Special Judge. The checker is provided by @[Lynkcat](https://www.luogu.com.cn/user/120911). Thanks for their contribution.** #### Notes Translated from [Croatian Olympiad in Informatics 2020 B Pastiri](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf). Translated by ChatGPT 5