Score : $600$ points

问题陈述

给定一棵包含 $N$ 个顶点的树 $T$，其中第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

构建一棵拥有 $N$ 个顶点的有根树 $R$，满足以下条件：

• 对于所有满足 $1 \leq x < y \leq N$ 的整数对 $(x,y)$，
  • 如果在树 $R$ 中顶点 $x$ 和 $y$ 的最低公共祖先为顶点 $z$，则在树 $T$ 中顶点 $z$ 位于顶点 $x$ 和 $y$ 之间的简单路径上。
• 在树 $R$ 中，对于除了根节点以外的所有顶点 $v$，以 $v$ 为根的子树的顶点数量乘以 $2$ 后，不超过以 $v$ 的父节点为根的子树的顶点数量。

我们可以证明，这样的有根树总是存在的。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a tree $T$ with $N$ vertices. The $i$-th edge connects vertices $A_i$ and $B_i$.

Construct an $N$-vertex rooted tree $R$ that satisfies the following conditions.

• For all integer pairs $(x,y)$ such that $1 \leq x < y \leq N$,
  • if the lowest common ancestor in $R$ of vertices $x$ and $y$ is vertex $z$, then vertex $z$ in $T$ is on the simple path between vertices $x$ and $y$.
• In $R$, for all vertices $v$ except for the root, the number of vertices of the subtree rooted at $v$, multiplied by $2$, does not exceed the number of vertices of the subtree rooted at the parent of $v$.

We can prove that such a rooted tree always exists.

Constraints

• $1 \leq N \leq 10^5$
• $1\leq A_i,B_i \leq N$
• All values in the input are integers.
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

Output

Let $R$ be a rooted tree that satisfies the conditions in the Problem Statement. Suppose that the parent of vertex $i$ in $R$ is vertex $p_i$. (If $i$ is the root, let $p_i=-1$.)
Print $N$ integers $p_1,\ldots,p_N$, with spaces in between.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 -1 4 2

For example, the lowest common ancestor in $R$ of vertices $1$ and $3$ is vertex $2$; in $T$, vertex $2$ is on the simple path between vertices $1$ and $3$.
Also, for example, in $R$, the subtree rooted at vertex $4$ has two vertices, and the number multiplied by two does not exceed the number of vertices of the subtree rooted at vertex $2$, which has $4$ vertices.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

-1 1 1 1 1

update @ 2024/3/10 12:10:13