/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
N 頂点の木があり、頂点には 1, 2, \dots, N と番号が振られています。i 番目 (1 \leq i \leq N-1) の辺は頂点 A_i と頂点 B_i を結んでいます。
木を見つけた E869120 君は、N 個の頂点それぞれに整数を書き込み、square1001 君を驚かせようとしています。彼を驚かせるためには、頂点 i に書かれた整数を E_i とするとき、次の条件を満たす必要があります。
条件1 E_i \geq 1 (1 \leq i \leq N) を満たす。
条件2 すべての組 (i, j) (1 \leq i < j \leq N) について、|E_i - E_j| \geq dist(i, j) を満たす。
条件3 条件 1・条件 2 を満たす中で、\max(E_1, E_2, \dots, E_N) の値が最小になる。
ただし、dist(i, j) は次の値を指します。
- 頂点 i から j への単純パス（同じ頂点を 2 度通らない経路）の長さ。
- つまり、単純パスを q_0 \to q_1 \to q_2 \to \cdots \to q_L（q_0 = i, q_L = j）とするときの L の値。
square1001 君を驚かせるような整数の書き方を 1 つ構成してください。
制約
- 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 を順に、空白で区切って 1 行で出力してください。
問題文の条件を満たす整数の書き込み方が複数存在する場合は、どれを出力しても正解となります。
E_1 E_2 \cdots E_{N}
入力例 1
2 1 2
出力例 1
2 1
頂点 1 に整数 2 を、頂点 2 に整数 1 を書き込んだ場合、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) は正解となります。
Score : 600 points
Problem Statement
We have a tree with N vertices, numbered 1, 2, \dots, N. The i-th edge (1 \leq i \leq N-1) connects Vertex A_i and Vertex B_i.
A boy E869120 found this tree and wants to write an integer in each vertex to surprise another boy square1001. For that, the following conditions need to be satisfied, where E_i is the integer written on Vertex i.
Condition 1: E_i \geq 1 (1 \leq i \leq N) holds.
Condition 2: |E_i - E_j| \geq dist(i, j) holds for every pair (i, j) (1 \leq i < j \leq N).
Condition 3: the value \max(E_1, E_2, \dots, E_N) should be minimized while satisfying Conditions 1 and 2.
Here, dist(i, j) is:
- the length of the simple path (the path without repetition of the same vertex) from Vertex i to j.
- In other words, it is the value L where the simple path is q_0 \to q_1 \to q_2 \to \cdots \to q_L (q_0 = i, q_L = j).
Construct one way to write integers that surprises square1001.
Constraints
- 2 \leq N \leq 200000
- 1 \leq A_i < B_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
Output
Print a line containing integers E_1, E_2, \cdots, E_N to write on the vertices, in this order, with space as separator.
If there are multiple ways to write integers that satisfy the conditions in the Problem Statement, any of them will be accepted.
E_1 E_2 \cdots E_{N}
Sample Input 1
2 1 2
Sample Output 1
2 1
If we write an integer 2 on Vertex 1 and an integer 1 on Vertex 2, we have dist(1, 2) = 1 and |E_1 - E_2| = 1, satisfying Condition 2.
The other conditions are also satisfied, so we can surprise square1001 this way.
(E_1, E_2) = (1, 2) will also be accepted.
Sample Input 2
4 1 2 1 4 2 3
Sample Output 2
3 2 1 4
(E_1, E_2, E_3, E_4) = (2, 3, 4, 1) will also be accepted.