P8428 [COI 2020] Pastiri

给定一棵 $N$ 点的树，点编号为 $1$ 到 $N$，现在在 $K$ 个点上有羊，你的任务是在树上分配一些牧羊人。 这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。 当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。 求一种牧羊人的分配方案使得牧羊人总数最小。

第一行两个整数 $N,K$ 代表树的点数和有羊的点数。 接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表树的一条边。 第 $N+1$ 行 $K$ 个整数 $o_i$，代表有羊的点的编号。

第一行一个整数 $X$ 代表牧羊人总数的最小值。 第二行 $X$ 个整数代表每个牧羊人分配到哪个点上。 如果有多种解，输出一种即可。

#### 样例 3 解释  #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（8 pts）：$1 \le N \le 5 \times 10^5$，任意一个点 $i$ 都与 $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$。 对于 $100\%$ 的数据，$1 \le K \le N$，$1 \le a_i,b_i \le N$，$1 \le o_i \le N$。 **本题使用 Special Judge，checker 提供者 @[Lynkcat](https://www.luogu.com.cn/user/120911)，感谢他的贡献。** #### 说明 翻译自 [Croatian Olympiad in Informatics 2020 B Pastiri](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。