25467번 - Putevi 다국어

문제

Zadano je stablo od $N$ čvorova označenim prirodnim brojevima od 1ドル$ do $N$. Čvor 2ドル$ povezan je sa čvorom 1ドル,ドル čvor 3ドル$ s čvorom 1ドル,ドル čvor 4ドル$ s jednim od dva svoja djelitelja manja od sebe 1ドル$ i 2ドル,ドル čvor 5ドル$ sa čvorom 1ドル,ドル čvor 6ドル$ s jednim od svoja 3ドル$ djelitelja manja od sebe 1ドル,ドル 2ドル$ i 3ドル,ドル itd.

Tvoj zadatak je za svaku duljinu puta od 1ドル$ do $N,ドル odrediti koliko postoji puteva te duljine.

입력

U prvom je retku prirodan broj $N$ (1ドル ≤ N ≤ 100,000円$), broj iz teksta zadatka.

U drugom retku je $N - 1$ prirodnih brojeva $P_i$ (1ドル ≤ P_i < N$), redom oznake čvorova s kojim su čvorovi 2ドル,ドル 3ドル,ドル 4ドル,ドル $\dots,ドル $N$ spojeni. Kao što je već rečeno, one moraju biti strogo manji djelitelji oznaka čvorova s kojim se spajaju.

출력

U jednom retku ispiši $N$ brojeva, za svaku duljinu puta od 1ドル$ do $N$ redom broj puteva te duljine.

제한

힌트

Opis trećeg probnog primjera:

Na slici desno prikazano je stablo iz primjera.

U tom stablo je 6ドル$ puteva duljine 1ドル,ドル to su putevi u kojima je samo jedan čvor.

Putevi duljine dva: $(1, 2),ドル $(1, 3),ドル $(2, 4),ドル $(1, 5)$ i $(3, 6)$.

Putevi duljine tri: $(1, 2, 4),ドル $(1, 3, 6),ドル $(2, 1, 3),ドル $(2, 1, 5)$ i $(3, 1, 5)$.

Putevi duljine četiri: $(2, 1, 3, 6),ドル $(4, 2, 1, 3),ドル $(4, 2, 1, 5)$ i $(5, 1, 3, 6)$.

Jedini put duljine pet: $(4, 2, 1, 3, 6)$.

Nema puteva duljine 6ドル$.