Problem
Mirko è diventato l'amministratore delegato di una grande azienda. L'azienda impiega N persone, che sono numerate da 1 a N, e lo stesso Mirko ha il numero 1. Tutti i dipendenti, tranne Mirko, hanno un capo. Un capo può avere diversi subordinati, ma non più di un capo.
Quando Mirko riceve un incarico dagli investitori, lo consegna al suo subordinato con il numero più basso. Quel subordinato lo passa anche al suo subordinato con il numero più basso, e così via, finché il lavoro non passa a un lavoratore sfortunato senza subordinati per completarlo.
Quel lavoratore riceve 1 moneta, il suo capo riceve 2 monete, il capo di quel capo riceve 3 monete e così via. Quindi colui che ha effettivamente svolto il lavoro si rende conto di quanto sia ingiusto questo sistema capitalista e lascia il lavoro.
Mirko riceve incarichi fino a quando rimane un solo dipendente nell'azienda — Mirko stesso. Quindi completa questo compito, riceve 1 moneta e lascia la società.
Si chiese quante monete avesse ricevuto in totale ogni ex dipendente. Aiutalo con questo.
Inserimento:
La prima riga contiene un numero naturale N (1 ≤ N ≤ 2·10
5) — il numero dei dipendenti della società. La riga successiva contiene N-1 numeri a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — numero del capo dell'i-esimo impiegato.
Uscita:
Stampa N numeri, l'i-esimo numero dovrebbe indicare quante monete ha ricevuto l'i-esimo dipendente.
Esempi:
| Input |
Uscita |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Spiegazioni:
Quanto segue è una descrizione del secondo esempio.
Mirko assegna il primo incarico all'operaio 2, che lo passa all'operaio 3, che completa l'incarico. Pertanto, il lavoratore 3 riceve una moneta, il lavoratore 2 — due monete, e l'operaio 1, lo stesso Mirko, — tre monete. Successivamente, l'impiegato 3 si dimette.
Mirko affida la seconda mansione all'operaio 2, che la passa all'operaio 4, che passa subito l'attività all'operaio 5, che completa l'attività. Successivamente, il lavoratore 5 riceve una moneta, il lavoratore 4 — due monete, lavoratore 2 — tre monete, e Mirko — quattro monete. L'impiegato 5 si licenzia.
Dopo aver completato la terza attività, il lavoratore 4 riceve una moneta, il lavoratore 2 — due monete, e Mirko — tre monete, dopodiché l'impiegato 4 si dimette.
Dopo aver completato il quarto compito, il lavoratore 2 riceve una moneta e Mirko — due monete, dopodiché il secondo dipendente si dimette.
Infine, il quinto compito viene eseguito dallo stesso Mirko, ricevendo una moneta per questo, dopodiché il processo si interrompe.
In totale, Mirko ha ricevuto 13 monete, un impiegato 2 — 8 monete, lavoratore 4 — 3 monete e lavoratori 3 e 5 — una moneta.