CF748F Santa Clauses and a Soccer Championship

国家 Treeland 有 $n$ 座城市，通过 $n-1$ 条双向公路连接起来，使得从任意一座城市出发都能通过这些公路到达其他任何城市。明年将要举办一场足球锦标赛，所有参赛者都是圣诞老人。共有 $2k$ 支球队，分别来自 $2k$ 个不同的城市。 在第一阶段，所有球队被分为 $k$ 对。每对之间要进行两场比赛：一场在第一支队伍的主场，另一场在第二支队伍的主场。因此，$2k$ 个城市各承办一场比赛。但是，球队的配对方案尚未确定。 此外，还需选择若干城市供球员居住。组织者希望用于安置球队的城市数量尽可能少。 没有人愿意在比赛期间长途旅行，因此如果某支队伍需要在城市 $u$ 和 $v$ 进行比赛，他们希望居住在 $u$ 和 $v$ 之间最短路径上的某座城市（包括 $u$ 或 $v$ 本身）。还有一个限制：同一对球队必须住在同一个城市。 总结一下，组织者希望把 $2k$ 支队伍分成 $k$ 对，并把他们安置在最少数量的城市 $m$，满足每对球队居住在他们主场之间最短路径上的同一城市。

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^{5}$，$2 \leq 2k \leq n$），分别表示 Treeland 的城市数量和球队对数。 接下来的 $n-1$ 行描述 Treeland 的公路：每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n, a \neq b$），表示城市 $a$ 和城市 $b$ 有一条公路相连。保证任意两座城市之间都存在路径。 最后一行包含 $2k$ 个不同的整数 $c_1, c_2, ..., c_{2k}$（$1 \leq c_i \leq n$），表示第 $i$ 支球队的主场所在城市。所有数均不同。

输出第一行为一个正整数 $m$，表示可用于安置球队的最少城市数。 第二行为 $m$ 个不同的数字 $d_1, d_2, ..., d_m$（$1 \leq d_i \leq n$），表示被选中的安置城市编号。 接下来 $k$ 行，每行输出 $3$ 个整数 $u_j, v_j, x_j$，其中 $u_j$ 和 $v_j$ 表示第 $j$ 对球队的主场城市编号，$x_j$ 表示他们应居住的城市。每个 $c_1, c_2, ..., c_{2k}$ 必须恰好在所有的 $u_j$、$v_j$ 中各出现一次。每个 $x_j$ 必须属于 $d_1, d_2, ..., d_m$。 如果有多种方案，输出任意一种即可。

在第一个样例中，组织者可以将所有的球队都安置在编号为 $2$ 的城市。如何配对球队不重要，因为所有条件都已满足：城市 $2$ 位于集合 $\{2,4,5,6\}$ 中任意两座城市的最短路径上。 由 ChatGPT 5 翻译