Distàncies a les fulles P38916


Statement
 

pdf   zip

thehtml

Un arbre és un graf no dirigit, connex i acíclic. Una fulla és un vèrtex que només té un veí. Donat un arbre, per a cada vèrtex x, digueu quina és la distància dx a la fulla de l’arbre més propera a x.

Entrada

L’entrada conté diversos casos. Cada cas comença amb el nombre de vèrtexs n, seguit de n − 1 parells x y indicant una aresta entre x i y. Suposeu 2 ≤ n ≤ 105, que els vèrtexs es numeren a partir de 0, i que les arestes donades efectivament formen un arbre.

Sortida

Per a cada cas, escriviu n línies amb d0, …, dn−1, seguides d’una línia amb 10 guions.

Public test cases

  • Input

    2
0 1

5
0 4
2 0
0 1
3 2

8
1 5
4 3
0 7
3 0
6 2
1 7
2 3

    Output

    0
0
----------
1
0
1
0
0
----------
2
1
1
1
0
0
0
2
----------
    • Information
    Author
    Félix Moreno
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++