Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_24_08 - Gęstość w drzewie

Masz dane drzewo zawierające n wierzchołków. Odległość między dwoma wierzchołkami to minimalna liczba krawędzi po których trzeba przejść, żeby dojść z jednego wierzchołka do drugiego. W szczególności odległość od wierzchołka do niego samego jest równa 0.

Zdefinijmy funkcję gęstości G(v, r) dla wierzchołka v oraz całkowitej nieujemnej liczby r. Niech ilość wierzchołków (z v włącznie) odległych od v o nie więcej niż r będzie równa m. Wtedy funkcja G(v, r) = m / (r + 1)2.

Dla każdego wierzchołka v znajdź takie r, że G(v, r) jest największe możliwe. Jeśli istnieje wiele poprawnych r, to wypisz to największe.

Wejście

W pierwszym wejściu masz daną liczbę wierzchołków n. (2 ≤ n ≤ 105).

Drzewo znajdujące się na wejściu jest ukorzenione w wierzchołku o indeksie 1. Na wejściu znajduje się n - 1 liczb. i'ta liczba ai przedstawia indeks wierzchołka będącego ojcem wierzchołka o indeksie i + 1 (1 ≤ ai  i).

Wyjście

Wypisz n liczb. i'ta liczba oznacza najlepsze r dla wierzchołka o indeksie i.

Przykład

Wejście:
11
1 2 2 4 4 4 4 6 9 1

Wyjście:
0 2 0 1 0 0 0 0 0 0 0

Dodane przez:Bartek
Data dodania:2015-08-26
Limit czasu wykonania programu:2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.