← 返回题目列表

AtCoder · arc117_d

D. 奇迹树

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一棵树 N 顶点,已编号 1, 2, \dots, N。的 i第边缘 (1 \leq i \leq N-1) 连接顶点 A_i 和顶点 B_i.

一个男孩 E869120 发现了这棵树,并想在每个顶点写入一个整数,以让另一个男孩 square1001 感到惊讶。为此,需要满足以下条件,其中 E_i 是写在 Vertex 上的整数 i.

条件1: E_i \geq 1 (1 \leq i \leq N) 成立。
条件2: |E_i - E_j| \geq dist(i, j) 对于每对都成立 (i, j) (1 \leq i < j \leq N).
条件3: 值 \max(E_1, E_2, \dots, E_N) 应在满足条件 1 和 2 的同时最小化。

在这里, dist(i, j) 是:

  • 从 Vertex 开始的简单路径(没有重复相同顶点的路径)的长度 i to j.
  • 换句话说,它是值 L 简单路径在哪里 q_0 \to q_1 \to q_2 \to \cdots \to q_L (q_0 = i, q_L = j).

构造一种令 square1001 惊讶的整数写入方法。

约束

  • 2 \leq N \leq 200000
  • 1 \leq A_i < B_i \leq N
  • 给定的图是一棵树。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

输出

打印包含整数的行 E_1, E_2, \cdots, E_N 按此顺序在顶点上书写,以空格作为分隔符。

如果有多种方法可以写入满足问题陈述中的条件的整数,则任何一种都将被接受。

E_1 E_2 \cdots E_{N}

示例输入 1

2
1 2

示例输出 1

2 1

如果我们写一个整数 顶点上的 2 在顶点上 1 和一个整数 1 在顶点上 2,我们有 dist(1, 2) = 1 和 |E_1 - E_2| = 1,满足条件2。

其他条件也满足了,所以我们可以这样给square1001一个惊喜。

(E_1, E_2) = (1, 2) 也将被接受。


示例输入 2

4
1 2
1 4
2 3

示例输出 2

3 2 1 4

(E_1, E_2, E_3, E_4) = (2, 3, 4, 1) 也将被接受。