201173: [AtCoder]ARC117 D - Miracle Tree

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给定一棵 $n$ 个节点的树,要求构造出一个点权序列 $E$,满足以下三个条件: 1.所有 $E_i\ge 1(1\le i\le n)$。 2.对于任意一组 $(i,j)(1 ≤ i < j ≤ N)$,使 $|E_i-E_j|\ge dist(i,j)$,$dist$ 即树上两点距离。 3.使 $E$ 中的最大值最小。

加入题单

上一题 下一题 算法标签: