CF786E ALT

ALT 是 Encore 星系中的一颗星球。人类统治着这颗星球，但由于某种原因，这里没有狗，因此人们一直很悲伤和沮丧。Rick 和 Morty 是宇宙慈善家，他们想让 ALT 星球的人们开心起来。 ALT 有 $n$ 个城市，编号为 $1$ 到 $n$，有 $n-1$ 条双向道路，编号为 $1$ 到 $n-1$。任意两个城市之间都可以通过这些道路互相到达。 ALT 上有两类人： 1. 守卫者。每条道路旁都住着一位守卫者，他负责守护这条道路。 2. 公民。每位公民住在某个城市，并在另一个城市上班。 在 ALT 上，每个人要么是守卫者，要么是公民，而且每条道路正好有一名守卫者。  Rick 和 Morty 与所有 ALT 的人交流后，得到了以下信息： - ALT 上有 $m$ 位公民。 - 第 $i$ 位公民住在第 $x_{i}$ 个城市，在第 $y_{i}$ 个城市工作。 - 每天，每位公民会经过家到办公室的最短路径上的所有道路。 - 只有当一位公民自己拥有一只小狗，或者他上班路上的所有守卫者都有一只小狗时，这位公民才会开心（他在路过每条道路时看到守卫者的小狗就会开心）。 - 每位守卫者总是开心的。 你需要告诉 Rick 和 Morty，最少需要多少只小狗，才能让所有 ALT 上的人都开心，并提供一种最优的小狗分配方式。

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \times 10^4$，$1 \leq m \leq 10^4$），分别表示城市的数量和公民的数量。 接下来的 $n-1$ 行描述道路，第 $i$ 行包含 $v$ 和 $u$（$1 \leq v,u \leq n$，$v \neq u$），表示第 $i$ 条道路连接城市 $v$ 和 $u$。 接下来的 $m$ 行描述公民信息，第 $i$ 行包含两个整数 $x_{i}$ 和 $y_{i}$（$1 \leq x_{i}, y_{i} \leq n$，$x_{i} \neq y_{i}$），表示第 $i$ 位公民住在城市 $x_{i}$，在城市 $y_{i}$ 上班。

输出第一行为一个整数 $k$，表示需要的小狗总数（$1\leq k\leq n$）。 第二行输出一个整数 $q$，表示需要分配给公民的小狗数量，后跟 $q$ 个不重复的正整数 $a_{1},a_{2},...,a_{q}$，表示需要给第 $a_{j}$ 位公民分配小狗（$0\leq q\leq \min(m,k)$，$1\leq a_{j}\leq m$）。 第三行输出一个整数 $e$，表示需要分配给守卫者的小狗数量，后跟 $e$ 个不重复的正整数 $b_{1},b_{2},...,b_{e}$，表示需要给第 $b_{j}$ 条道路的守卫者分配小狗（$0\leq e\leq \min(n-1,k)$，$1\leq b_{j}\leq n-1$）。 要求 $q+e=k$。

第一个样例的 ALT 地图如下（道路上的数字为其编号）：  第二个样例的 ALT 地图如下（道路上的数字为其编号）：  由 ChatGPT 5 翻译