← 返回题目列表

AtCoder · abc291_h

Ex. 平衡树

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你得到一棵树 T 与 N 顶点。 的 i第一条边连接顶点 A_i 和 B_i.

构建一个 N- 顶点有根树 R 满足以下条件。

  • 对于所有整数对 (x,y) 这样 1 \leq x < y \leq N,
    • 如果最低共同祖先在 R 顶点数 x 和 y 是顶点 z,然后顶点 z in T 位于顶点之间的简单路径上 x 和 y.
  • In R,对于所有顶点 v 除根外,以子树为根的子树的顶点数 v,乘以 2,不超过以父级为根的子树的顶点数 v.

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

约束

  • 1 \leq N \leq 10^5
  • 1\leq A_i,B_i \leq N
  • 输入中的所有值都是整数。
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

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

输出

让 R 是满足问题陈述中的条件的有根树。 假设顶点的父节点 i in R 是顶点 p_i。 (如果 i 是根,让 p_i=-1.)
打印 N 整数 p_1,\ldots,p_N,中间有空格。


示例输入 1

4
1 2
2 3
3 4

示例输出 1

2 -1 4 2

例如,最低共同祖先 R 顶点数 1 和 3 是顶点 2;在 T,顶点 2 位于顶点之间的简单路径上 1 和 3.
另外,例如,在 R,以顶点为根的子树 4 有两个顶点,且数量乘以2不超过以顶点为根的子树的顶点数 2,其中有 4 顶点。

Figure


示例输入 2

5
1 2
1 3
1 4
1 5

示例输出 2

-1 1 1 1 1