← 返回题目列表

Codeforces · 1056/D

D. 装饰苹果树

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

阿尔卡迪的花园里有一棵苹果树。它可以表示为一组与分支连接的交汇点,因此只有一种方法可以使用分支从任何其他交汇点到达任何交汇点。结点从 $$$1$$$ 到 $$$n$$$ 枚举,结点 $$$1$$$ 称为根。

结点 $$$v$$$ 的子树是结点 $$$u$$$ 的集合,使得从 $$$u$$$ 到根的路径必须经过 $$$v$$$。请注意,$$$v$$$ 本身包含在 $$$v$$$ 的子树中。

叶子是一种结点,其子树恰好包含一个结点。

新年快到了,阿尔卡迪想要装饰这棵树。他会在每个叶子连接处放一个某种颜色的灯泡,然后计算快乐连接处的数量。快乐交汇点是 $$$t$$$ 子树中的所有灯泡都具有不同颜色的交汇点。

Arkady 对以下问题感兴趣:对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,使快乐连接点的数量大于或等于 $$$k$$$ 所需的不同颜色的最小数量是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 树中的结点数量。

第二行包含 $$$n - 1$$$ 整数 $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i < i$$$),其中 $$$p_i$$$ 表示结点 $$$i$$$ 和 $$$p_i$$$ 之间存在分支。保证这组分支形成一棵树。

输出

输出 $$$n$$$ 个整数。其中第 $$$i$$$ 应该是使快乐连接点的数量至少为 $$$i$$$ 所需的最小颜色数。

示例

输入 #1

3
1 1

输出 #1

1 1 2

输入 #2

5
1 1 3 3

输出 #2

1 1 1 2 3

注意

在 $$$k = 1$$$ 和 $$$k = 2$$$ 的第一个示例中,我们只能使用一种颜色:连接点 $$$2$$$ 和 $$$3$$$ 会很高兴。对于$$$k = 3$$$,你必须放置不同颜色的灯泡以使所有的路口都满意。

在 $$$k = 4$$$ 的第二个示例中,您可以将颜色为 $$$1$$$ 的灯泡放入连接点 $$$2$$$ 和 $$$4$$$ 中,并将颜色为 $$$2$$$ 的灯泡放入连接点 $$$5$$$ 中。幸福的交汇点是索引为 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$ 的交汇点。