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

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.