Decorate Apple Tree

题意翻译

### 题目大意 给你一个$n$个结点以$1$为根的树，给这$n$个结点任意染色，定义一个点为快乐结点当且仅当这个结点的子树上所有点颜色均不相同。求出对于$1\sim n$中的每一个$k$，快乐结点数大于等于$k$所需要的最少颜色数。 ### 输入格式 第一行一个数$n(1\le n\le 10^5)$，表示结点数量 第二行$n-1$个数$p_i$，表示第$i$个结点的父亲结点$(1\le p_i<i)$ ### 输出格式 一行，$n$个数，表示对于$1\sim n$中的每一个$k$，快乐节点数大于等于$k$时所需的最少颜色数

题目描述

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

输入输出样例

输入样例 #1

3
1 1

输出样例 #1

1 1 2 

输入样例 #2

5
1 1 3 3

输出样例 #2

1 1 1 2 3 

说明

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.