Problem
Mirko se convirtió en el director ejecutivo de una gran corporación. La empresa emplea a N personas, que están numeradas del 1 al N, y el propio Mirko tiene el número 1. Todos los empleados, excepto Mirko, tienen un jefe. Un jefe puede tener varios subordinados, pero no más de un jefe.
Cuando Mirko recibe una asignación de los inversores, se la entrega a su subordinado con el número más bajo. Ese subordinado también lo pasa a su subordinado con el número más bajo, y así sucesivamente, hasta que el trabajo pasa a un desafortunado trabajador sin subordinados para completarlo.
Ese trabajador recibe 1 moneda, su jefe recibe 2 monedas, el jefe de ese jefe recibe 3 monedas y así sucesivamente. Luego, el que realmente hizo el trabajo se da cuenta de lo injusto que es este sistema capitalista y renuncia al trabajo.
Mirko recibe asignaciones hasta que solo queda un empleado en la corporación — El propio Mirko. Luego completa esta tarea, recibe 1 moneda y deja la corporación.
Se preguntó cuántas monedas recibió cada ex empleado en total. Ayúdalo con esto.
Entrada:
La primera línea contiene un número natural N (1 ≤ N ≤ 2·10
5) — el número de empleados de la empresa. La siguiente línea contiene N-1 números a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — número del jefe del i-ésimo empleado.
Salida:
Escriba N números, el i-ésimo número debe indicar cuántas monedas recibió el i-ésimo empleado.
Ejemplos:
| Entrada |
Salida |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Explicaciones:
La siguiente es una descripción del segundo ejemplo.
Mirko le da la primera tarea al trabajador 2, quien se la pasa al trabajador 3, quien completa la tarea. Así, el trabajador 3 recibe una moneda, el trabajador 2 — dos monedas, y el trabajador 1, el mismo Mirko, — tres monedas Después de eso, el empleado 3 renuncia.
Mirko le da la segunda tarea al trabajador 2, quien se la pasa al trabajador 4, quien inmediatamente pasa la tarea al trabajador 5, quien la completa. Después de eso, el trabajador 5 recibe una moneda, el trabajador 4 — dos monedas, trabajador 2 — tres monedas, y Mirko — cuatro monedas El empleado 5 renuncia.
Después de completar la tercera tarea, el trabajador 4 recibe una moneda, el trabajador 2 — dos monedas y Mirko — tres monedas, después de lo cual el empleado 4 renuncia.
Después de completar la cuarta tarea, el trabajador 2 recibe una moneda y Mirko — dos monedas, después de lo cual el segundo empleado renuncia.
Finalmente, la quinta tarea la realiza el mismo Mirko, recibiendo una moneda por esto, después de lo cual el proceso se detiene.
En total, Mirko recibió 13 monedas, un empleado 2 — 8 monedas, trabajador 4 — 3 monedas, y trabajadores 3 y 5 – mdash; una moneda