Árboles P98551
Como es bien sabido, un grafo (no dirigido) consiste en un conjunto de vértices y un conjunto de aristas entre pares de vértices. Un árbol es un tipo especial de grafo: uno que es conexo y sin ciclos (es decir, con exactamente un camino entre todo par de vértices). Si un árbol tiene n vértices, entonces su número de aristas tiene que ser n − 1. Por ejemplo, éste es un árbol con 10 vértices, etiquetados entre 0 y 9:
(106,90)
(6,76)3 (26,76)3 (26,46)3 (40,60)3 (60,80)3 (60,60)3 (80,60)3 (80,80)3 (100,60)3 (80,40)3
(9,76)(23,76) (28,74)(38,62) (28,48)(38,58) (43,60)(57,60) (60,63)(60,77) (63,60)(77,60) (80,63)(80,77) (83,60)(97,60) (80,57)(80,43)
(6,76)3 (26,76)0 (26,46)5 (40,60)4 (60,80)8 (60,60)7 (80,60)2 (80,80)6 (100,60)1 (80,40)9
El motivo por el que los árboles se llaman así es que, si se escoge un vértice como raíz, y se hace que los demás vértices “cuelguen” del vértice escogido, la forma obtenida se asemeja a un árbol de la naturaleza (excepto que está del revés, con la raíz arriba, ramificándose hacia abajo, y con las hojas en los extremos inferiores). Siguiendo con el ejemplo, éstos son los resultados de escoger como raíz el vértice 0 y el vértice 7:
Definamos el tamaño de un árbol (o de un subárbol) como su número de vértices. Vuestra tarea es decidir qué vértice escoger como raíz, de manera que el mayor de los subárboles de la raíz sea tan pequeño como sea posible.
Por ejemplo, del árbol de la izquierda, el subárbol izquierdo tiene un vértice, y el subárbol derecho tiene ocho vértices. En cambio, de los tres subárboles del árbol de la derecha, uno tiene un vértice, y los otros dos tienen cuatro vértices. Así pues, el máximo de los tamaños de los subárboles es ocho y cuatro, respectivamente. De hecho, de las diez raíces posibles, el 7 es la que tiene el mínimo subárbol máximo.
Entrada
La entrada consiste en como mucho 1000 casos. Cada caso consiste en el número de vértices n seguido de las n − 1 aristas, en forma de pares de vértices. Suponed n ≥ 2, y que los vértices se numeran entre 0 y n − 1.
Salida
Para cada árbol dado, escribid el mínimo tamaño posible del subárbol máximo de la raíz, si se escoge la raíz convenientemente. Tu programa tiene 1 segundo de CPU para resolver cada entrada.
Puntuación
- TestA: Entradas donde n es como mucho 4. 20 Puntos
- TestA: Entradas donde n es como mucho 10. 20 Puntos
- TestA: Entradas donde n es como mucho 100. 20 Puntos
- TestA: Entradas donde n es como mucho 1000. 20 Puntos
- TestA: Entradas donde n es como mucho 10000. 20 Puntos
Input
3 1 2 0 1 4 1 3 3 0 0 2 4 0 2 2 1 0 3 4 1 0 2 0 0 3 6 1 3 2 0 3 4 2 5 4 2 10 9 2 4 5 4 0 7 8 3 0 6 2 1 2 2 7 4 7
Output
1 2 2 1 3 4
- Author
- Salvador Roura
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++