Famille de grenouilles – Regional event 2017

Level 5

Énoncé

Lors de sa petite marche matinale, Joseph Marchand tombe sur un étang plein de grenouilles. Ces grenouilles sont assez particulières : chacune possède un unique parent, aussi présent dans l'étang, à l'exception de l'unique plus ancienne des grenouilles, qui elle n'en a pas.

Elles lui disent, l'une après l'autre, qui sont leurs parents. Joseph note cela très précieusement dans son petit journal de voyage. Il se fait la remarque alors qu'il doit y avoir un sacré nombre de cousines dans l'étang !

Une grenouille est dite cousine d'une seconde d'ancienneté $p$, ou $p$-cousine, si leur plus jeune ancêtre commun est leur $p$-ancêtre. Par exemple des 1-cousines sont des sœurs.

Une grenouille est une p-ancêtre d'une autre si elles sont séparées par p degrés de parenté : une parente est une 1-ancêtre, une grand-parente est une 2-ancêtre, et ainsi de suite.

Joseph souhaite établir alors la liste des $p$-cousines pour chaque $p$ possible.

Aidez Joseph en lui donnant le nombre de couples (non ordonnés) de $p$-cousines pour chaque $p$ entre 1 et 10 (il n'y a pas plus de 11 générations de grenouilles dans l'étang).

Les grenouilles sont numérotées de 0 à $N - 1$, la grenouille 0 étant la plus ancienne.

Entrée

L'entrée comprendra plusieurs lignes :

  • La première ligne contiendra un entier $N$, le nombre total de grenouille
  • $N - 1$ lignes suivent, la i-ème d'entre elles donnera le numéro de la grenouille parente de la grenouille $i$.

Sortie

Vous afficherez 10 lignes, la i-ème ligne contiendra le nombre de couples de $i$-cousines.

Contraintes

  • $1 \le N \le 500$

Contraintes de performance

  • $1 \le N \le 100\ 000$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
7
0
0
1
1
2
2
Sample output
3
4
0
0
0
0
0
0
0
0
Sample input
9
0
1
2
3
0
5
6
7
Sample output
1
1
1
1
0
0
0
0
0
0

Submit your solution

You have to register or log in to be able to submit your solution.