CF1073F Choosing Two Paths

给定一棵包含 $n$ 个顶点的无向无权树。 无向树是一个连通的无向图，包含 $n-1$ 条边。 你的任务是从这棵树中选择两对顶点（所有被选中的顶点都必须互不相同），即 $(x_1, y_1)$ 和 $(x_2, y_2)$，使得 $x_1$ 和 $y_1$ 都不在从 $x_2$ 到 $y_2$ 的简单路径上，反之亦然（即 $x_2$ 和 $y_2$ 也都不在从 $x_1$ 到 $y_1$ 的简单路径上）。 保证对于给定的树一定可以选择出满足条件的两对顶点。 在所有可能的选择方案中，你需要选择一组，使得从 $x_1$ 到 $y_1$ 的路径与从 $x_2$ 到 $y_2$ 的路径的公共顶点数最大。在所有公共顶点数最大的方案中，再选择一组使得这两条路径的总长度最大。 保证对于给定的树，存在至少有两个公共顶点的答案。 路径的长度是指路径上的边数。 简单路径是指每个顶点最多只经过一次的路径。

第一行包含一个整数 $n$，表示树的顶点数（$6 \le n \le 2 \times 10^5$）。 接下来的 $n-1$ 行，每行描述树中的一条边。 第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，表示该边连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。 保证给定的边构成一棵树。 保证存在至少有两个公共顶点的答案。

输出任意一组满足题目要求的两对顶点。 保证一定存在满足条件的选择方案。

第一个样例对应的图如下： 两条路径的交集为 $2$（顶点 $1$ 和 $4$），总长度为 $4+3=7$。 第二个样例对应的图如下： 两条路径的交集为 $2$（顶点 $3$ 和 $4$），总长度为 $5+3=8$。 第三个样例对应的图如下： 两条路径的交集为 $3$（顶点 $2$、$7$ 和 $8$），总长度为 $5+5=10$。 第四个样例对应的图如下： 两条路径的交集为 $5$（顶点 $1$、$2$、$3$、$4$ 和 $5$），总长度为 $6+6=12$。 由 ChatGPT 4.1 翻译