Problem
Mirko est devenu le PDG d'une grande entreprise. L'entreprise emploie N personnes, qui sont numérotées de 1 à N, et Mirko lui-même a le numéro 1. Tous les employés, sauf Mirko, ont un patron. Un patron peut avoir plusieurs subordonnés, mais pas plus d'un patron.
Lorsque Mirko reçoit une mission d'investisseurs, il la remet à son subordonné avec le numéro le plus bas. Ce subordonné le transmet également à son subordonné ayant le numéro le plus bas, et ainsi de suite, jusqu'à ce que le travail passe à un travailleur malchanceux sans subordonné pour le terminer.
Cet ouvrier reçoit 1 pièce, son patron reçoit 2 pièces, le patron de ce patron reçoit 3 pièces, et ainsi de suite. Ensuite, celui qui a réellement fait le travail réalise à quel point ce système capitaliste est injuste et quitte le travail.
Mirko reçoit des affectations jusqu'à ce qu'il ne reste qu'un seul employé dans l'entreprise — Mirko lui-même. Ensuite, il termine cette tâche, reçoit 1 pièce et quitte la société.
Il se demandait combien de pièces chaque ancien employé recevait au total. Aidez-le avec ça.
Saisie :
La première ligne contient un nombre naturel N (1 ≤ N ≤ 2·10
5) — le nombre d'employés de l'entreprise. La ligne suivante contient N-1 nombres a
2, a
3,... a
n (1 ≤ a
je <i), un
je — numéro du chef du ième employé.
Sortie :
Imprimez N chiffres, le ième chiffre doit indiquer combien de pièces le ième employé a reçu.
Exemples :
| Entrée |
Sortie |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Explications :
Voici une description du deuxième exemple.
Mirko donne la première tâche au travailleur 2, qui la transmet au travailleur 3, qui termine la tâche. Ainsi, le travailleur 3 reçoit une pièce, le travailleur 2 — deux pièces, et le travailleur 1, Mirko lui-même, — trois pièces. Après cela, l'employé 3 démissionne.
Mirko donne la deuxième tâche au travailleur 2, qui la transmet au travailleur 4, qui passe immédiatement la tâche au travailleur 5, qui termine la tâche. Après cela, le travailleur 5 reçoit une pièce, le travailleur 4 — deux pièces, travailleur 2 — trois pièces, et Mirko — quatre pièces. L'employé 5 démissionne.
Après avoir terminé la troisième tâche, le travailleur 4 reçoit une pièce, le travailleur 2 — deux pièces, et Mirko — trois pièces, après quoi l'employé 4 quitte.
Après avoir terminé la quatrième tâche, le travailleur 2 reçoit une pièce et Mirko — deux pièces, après quoi le deuxième employé quitte.
Enfin, la cinquième tâche est effectuée par Mirko lui-même, recevant une pièce pour cela, après quoi le processus s'arrête.
Au total, Mirko a reçu 13 pièces, un employé 2 — 8 pièces, travailleur 4 — 3 pièces, et ouvriers 3 et 5 — une pièce.