A12112 | Decorate Apple Tree

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$ ?

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 $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$ .