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++