codeforces#P1056D. Decorate Apple Tree
Decorate Apple Tree
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$?
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$.
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$.
Samples
3
1 1
1 1 2
5
1 1 3 3
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.