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 \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 翻译