Decorate Apple Tree
Contest: Mail.Ru Cup 2018 Round 3
Difficulty rating: 1600
Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, sortings, trees

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
3
1 1

Example output:
1 1 2

Example input:
5
1 1 3 3

Example output:
1 1 1 2 3

Editorial:
I'll try two describe two different approaches to this problem.
• A more intuitive solution. We are asked to output the number of colors for all $$$k$$$, let's reverse the problem and count the maximum $$$k$$$ for all possible number of colors $$$c$$$. We can see that if we a junction is happy then all junctions in its subtree are also happy. So we're interested in selecting some set of junctions so that their subtrees are disjoint and have no more than $$$c$$$ leaves, and we want to maximize the total size of these subtrees. This can be done greedily from the root: if a subtree is small enough, take it all, in the other case go to its children instead. We can see that a subtree is in the answer set for all $$$c$$$ not less than the size of the subtree and less than the size of the parent's subtree. We can easily compute this range for all junction in one deep-first search and sum the answer on these segments.
• A more professional solution. Note that a junction can be happy only when the number of colors is at least the number of leaves in it. The rule is that this is the only condition needed: indeed, if we color the leaves cyclically in the order of Euler tour, all such junctions will be happy. So the answer for the number of colors is simply the number of junctions that have at most $$$c$$$ leaves in the subtree
Both solutions can be implemented in $$$O(n)$$$.