CF1340D Nastya and Time Machine

Denis 来找 Nastya，却发现她并不高兴见到他……只有一个办法能让她开心。Denis 想要买下 Nastya 喜欢的所有东西，这样她就一定会同意和他说话。 他们居住的城市地图上有许多广场，其中一些通过道路相连。任意一对广场之间恰好有一条不重复经过任何顶点的路径。也就是说，这座城市的图是一棵树。 Denis 在时间 $0$ 时位于顶点 $1$。他想要尽快遍历每一个顶点至少一次，并返回起点。 Denis 走一条道路需要 $1$ 单位时间。不幸的是，这座城市太大了，想要遍历所有广场需要很长时间。因此，Denis 做出了一个大胆的决定。他拿出了自己在地下室制造的袖珍时光机。借助它，Denis 可以将当前时间更改为任意小于当前时间的非负整数。 但时光机有一个特点。如果 Denis 在同一个地方、同一时刻出现两次，将会发生宇宙级别的大爆炸，Nastya 也将永远不开心。因此，Denis 请求你帮他规划一条路线，利用时光机遍历所有广场，并返回起点，同时使他在任意广场访问时的最大时间尽可能小。 形式化地，Denis 的路线可以表示为一系列对：$\{v_1, t_1\}, \{v_2, t_2\}, \{v_3, t_3\}, \ldots, \{v_k, t_k\}$，其中 $v_i$ 表示广场编号，$t_i$ 表示此时 Denis 所在的时间。 需要满足以下条件： - 路线从广场 $1$ 的时间 $0$ 开始，即 $v_1 = 1, t_1 = 0$，并以广场 $1$ 结束，即 $v_k = 1$。 - 所有转移分为两种类型： 1. 在同一广场改变时间：$\{v_i, t_i\} \to \{v_{i+1}, t_{i+1}\}$，其中 $v_{i+1} = v_i, 0 \leq t_{i+1} < t_i$。 2. 沿道路行走：$\{v_i, t_i\} \to \{v_{i+1}, t_{i+1}\}$，其中 $v_i$ 和 $v_{i+1}$ 通过道路相连，且 $t_{i+1} = t_i + 1$。 - 所有的 $\{v_i, t_i\}$ 对必须互不相同。 - 所有广场都必须出现在 $v_1, v_2, \ldots, v_k$ 中。 你需要找到一条路线，使得在任意广场访问时的最大时间最小，即使得 $\max{(t_1, t_2, \ldots, t_k)}$ 尽可能小。

第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示城市中的广场数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ $(1 \leq u, v \leq n, u \neq v)$，表示编号为 $u$ 和 $v$ 的广场之间有一条道路。 保证给定的图是一棵树。

第一行输出一个整数 $k$ $(1 \leq k \leq 10^6)$，表示 Denis 路线的长度。 接下来的 $k$ 行，每行输出一对 $v_i, t_i$，描述 Denis 的路线（如题目描述）。 必须满足题目中所有关于路线的要求。 保证在给定限制下至少存在一条合法路线，且答案的长度不超过 $10^6$。如果有多种合法答案，输出任意一种即可。

由 ChatGPT 4.1 翻译