AT_abc291_h [ABC291Ex] Balanced Tree

题目描述

给定一棵有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

请你构造一棵满足以下两个条件的、有 $N$ 个顶点的有根树 $R$：

• 对于所有满足 $1 \leq x < y \leq N$ 的整数对 $(x, y)$，都满足：
  • 若 $R$ 中顶点 $x$ 和 $y$ 的最近公共祖先为顶点 $z$，则在 $T$ 中连接顶点 $x$ 和 $y$ 的简单路径上存在顶点 $z$。
• 在 $R$ 中，对于除根以外的每个顶点 $v$，以 $v$ 为根的子树的顶点数的 $2$ 倍，不超过以 $v$ 的父亲为根的子树的顶点数。

可以证明，满足上述条件的有根树一定存在。

输入格式

输入按以下格式从标准输入读入。

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

设 $R$ 为满足条件的有根树。令 $p_i$ 表示 $R$ 中顶点 $i$ 的父亲（若 $i$ 为根，则 $p_i = -1$）。
请按顺序输出 $N$ 个整数 $p_1, p_2, \ldots, p_N$，用空格分隔。

输入输出样例 #1

输入 #1

4
1 2
2 3
3 4

输出 #1

2 -1 4 2

输入输出样例 #2

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

-1 1 1 1 1

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• 输入均为整数
• 给定的图为一棵树

样例解释 1

例如，$R$ 中顶点 $1, 3$ 的最近公共祖先为顶点 $2$，并且在 $T$ 中连接顶点 $1$ 和 $3$ 的简单路径上存在顶点 $2$。
又如，$R$ 中以顶点 $4$ 为根的子树的顶点数为 $2$，其 $2$ 倍为 $4$，不超过以顶点 $2$ 为根的子树的顶点数 $4$。

由 ChatGPT 4.1 翻译