Background

$\texttt{I'm getting tired of hiding.}$

Statement: The image above is taken from the Internet, pid:6544352. If there is any infringement, please inform us and it will be deleted.

Problem Description

Given a rooted tree with $n$ nodes, where the root is node $1$. Let the subtree rooted at $i$ be $T_i$. You need to assign each node a positive integer weight $v_i$ such that all node weights are exactly $1,2,\dots,n$, each used once.

Define

$$f=\sum_{i=1}^{n}R_i,$$

where $R_i$ is the range of weights in the subtree rooted at $i$, i.e.

$$R_i=\max_{j \in T_i}\{v_j\}-\min_{j \in T_i}\{v_j\}.$$

Among all valid assignments, find one assignment of node weights that minimizes $f$.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between $u$ and $v$.

Output Format

Output one permutation of $1,2,\dots,n$, representing the node weights of nodes $1,2,\dots,n$. Since there may be many valid assignments, you only need to output any one of them.

3
1 2
1 3

1 2 3

2
1 2

1 2

5
1 2
2 3
3 4
4 5

1 2 3 4 5

Hint

Sample Explanation

Input $\#1$

$R_1=3-1=2,R_2=2-2=0,R_3=3-3=0,f=R_1+R_2+R_3=2$. It can be proven that there is no construction that makes $f$ smaller.

---

Constraints

For $10\%$ of the testdata, $n \le 10$.

For another $10\%$ of the testdata, the tree is a chain.

For another $20\%$ of the testdata, there is one node connected to the other $n-1$ nodes.

For another $20\%$ of the testdata, the tree is a complete binary tree, meaning every non-leaf node has exactly two children.

For $100\%$ of the testdata, $1 \le n \le 10^6$.

Translated by ChatGPT 5