CF2253E Diameter Intersections

给定一棵有 $n$ 个节点的树。树的直径是指树中长度最长的简单路径。路径的长度是其包含的边的数量。已知给定的树的直径长度是奇数。 称一个整数 $k$ 是“美丽的”，如果存在两条树的直径（可以有相同的两个端点，也允许选择同一条直径），使得它们的交集中恰好包含 $k$ 条边。 请找出所有美丽的 $k$ 值，并按照递增顺序输出。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例按照以下格式给出： - 第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示树的节点数； - 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示节点 $u$ 与节点 $v$ 之间有一条边。 输入额外保证： - 所有测试用例的 $n$ 之和不超过 $10^6$； - 每个测试用例给出的边集保证构成一棵直径长度为奇数的树。

对于每个测试用例，输出一行，先输出一个整数 $m$，表示美丽的 $k$ 的数量；然后输出所有美丽的 $k$ 值，按升序排列。

考虑前面三个示例： - 在第一个示例中，选取直径 $(1, 2)$ 和 $(1, 2)$，交集包含 $k=1$ 条边； - 在第二个示例中，选取直径 $(1, 4)$ 和 $(4, 1)$，交集包含 $k=3$ 条边； - 在第三个示例中，选取直径 $(6, 4)$ 和 $(3, 5)$，交集包含 $k=1$ 条边；选取 $(6, 4)$ 和 $(4, 5)$，交集包含 $k=2$ 条边；选取 $(6, 4)$ 和 $(6, 4)$，交集包含 $k=3$ 条边。 由 ChatGPT 5 翻译