Hormigas en el Árbol

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Un árbol es un grafo conexo sin ciclos. Una hoja de un árbol es un nodo con grado \(1\) (excepto la raíz).

En un parque hay un árbol con \(n\) nodos y el nodo \(1\) es su raíz. Hay una hormiga en cada hoja del árbol. En una unidad de tiempo las hormigas pueden ir (simultáneamente) desde el nodo en el que están hacia su nodo padre, con la restricción de que no pueden haber dos hormigas al mismo tiempo en el mismo nodo, excepto en la raíz.

Tu tarea es calcular el tiempo mínimo en el que todas las hormigas pueden llegar a la raíz.

Entrada

La primera línea de la entrada contiene el entero \(n \; (1 \leq n \leq 10^5)\).

Las siguientes \(n - 1\) líneas contienen una arista del árbol de la forma \(x_i \; y_i \; (1 \leq x_i, y_i \leq n)\).

Salida

En una única línea imprima el tiempo mínimo para que todas las hormigas lleguen a la raíz.

Ejemplos

Entrada 1
12
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
8 10
8 11
8 12
Salida 1
6
Entrada 2
2
2 1
Salida 2
1

Comments

There are no comments at the moment.