CF1278E Tests for problem D

我们在为 D 题生成测试数据时遇到了很大的困难。为了准备强有力的测试数据，我们不得不解决如下问题。 给定一个包含 $n$ 个顶点的无向有标号树，请你找到一组线段集合，满足以下条件： 1. 每条线段的两个端点都是 $1$ 到 $2n$ 之间的整数，并且每个 $1$ 到 $2n$ 的整数恰好作为某一条线段的一个端点出现一次； 2. 所有线段都是非退化的（即每条线段的两个端点不相等）； 3. 对于每一对 $i \ne j$，其中 $i \in [1, n]$，$j \in [1, n]$，当且仅当顶点 $i$ 和 $j$ 在树中有一条边直接相连时，第 $i$ 条线段和第 $j$ 条线段相交，且不存在一条线段完全包含另一条线段。 你能解决这个问题吗？

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示树的顶点数。 接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示第 $i$ 条边的两个端点。 保证给定的图是一棵树。

输出 $n$ 对整数，第 $i$ 对包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le 2n$），表示第 $i$ 条线段的两个端点。你输出的 $2n$ 个整数必须各不相同。 保证一定存在解。

由 ChatGPT 4.1 翻译