Decorate Apple Tree

1000ms

262144K

Description:

There is one apple tree in Arkady's garden. It can be represented as a set of junctions connected with branches so that there is only one way to reach any junctions from any other one using branches. The junctions are enumerated from $$$1$$$ to $$$n$$$, the junction $$$1$$$ is called the root.

A subtree of a junction $$$v$$$ is a set of junctions $$$u$$$ such that the path from $$$u$$$ to the root must pass through $$$v$$$. Note that $$$v$$$ itself is included in a subtree of $$$v$$$.

A leaf is such a junction that its subtree contains exactly one junction.

The New Year is coming, so Arkady wants to decorate the tree. He will put a light bulb of some color on each leaf junction and then count the number happy junctions. A happy junction is such a junction $$$t$$$ that all light bulbs in the subtree of $$$t$$$ have different colors.

Arkady is interested in the following question: for each $$$k$$$ from $$$1$$$ to $$$n$$$, what is the minimum number of different colors needed to make the number of happy junctions be greater than or equal to $$$k$$$?

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of junctions in the tree.

The second line contains $$$n - 1$$$ integers $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i < i$$$), where $$$p_i$$$ means there is a branch between junctions $$$i$$$ and $$$p_i$$$. It is guaranteed that this set of branches forms a tree.

Output:

Output $$$n$$$ integers. The $$$i$$$-th of them should be the minimum number of colors needed to make the number of happy junctions be at least $$$i$$$.

Sample Input:

3
1 1

Sample Output:

1 1 2

Sample Input:

5
1 1 3 3

Sample Output:

1 1 1 2 3

Note:

In the first example for $$$k = 1$$$ and $$$k = 2$$$ we can use only one color: the junctions $$$2$$$ and $$$3$$$ will be happy. For $$$k = 3$$$ you have to put the bulbs of different colors to make all the junctions happy.

In the second example for $$$k = 4$$$ you can, for example, put the bulbs of color $$$1$$$ in junctions $$$2$$$ and $$$4$$$, and a bulb of color $$$2$$$ into junction $$$5$$$. The happy junctions are the ones with indices $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ then.

Informação

Provedor Codeforces

Código CF1056D