Decorate Apple Tree (Codeforces 1056D)
Tags: Greedy, 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: 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$$$.

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.

Sample Inputs:
3
1 1

5
1 1 3 3

Sample Outputs:
1 1 2

1 1 1 2 3

Solution (Python):
n = int(input())
d = [0, 0] + [int(x) for x in input().split()]
graph = {}
for i in range(2, n + 1):
    if d[i] in graph:
        graph[d[i]].append(i)
    else:
        graph[d[i]] = [i]
vis = [0] * (n + 1)
for i in range(n, 1, -1):
    if i not in graph:
        vis[i] = 1
        vis[d[i]] += 1
    else:
        vis[d[i]] += vis[i]
vis.sort()
if n == 1:
    print(1)
else:
    print(*vis[1:])

Solution (Python):
n = int(input())
p = [0, 0] + list(map(int, input().split()))
d = [0] * (n + 1)
for i in range(n, 1, -1):
    if d[i] == 0:
        d[i] = 1
    d[p[i]] += d[i]
if n == 1:
    d[1] = 1
d = d[1:]
d.sort()
print(*d)

Solution (Python):
n = int(input())
p = [0, 0] + list(map(int, input().split()))
d = [0] * (n + 1)
for i in range(n, 1, -1):
    if d[i] == 0:
        d[i] = 1
    d[p[i]] += d[i]
if n == 1:
    d[1] = 1
d = d[1:]
d.sort()
print(*d)