P8578 [CoE R5] So What Do We Do Now?

 >$\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.

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$.

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 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.

**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