Tala de Árboles


Submit solution

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

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Después de que el Granjero Juan (GJ) se dio cuenta de que Bessie había instalado una red en "forma de árbol" entre sus N (1 \leq N \leq 10 000) graneros a un costo increíble, demandó a Bessie para mitigar sus pérdidas.

Bessie, sintiéndose vengativa, decidió sabotear la red del Granjero Juan cortando la energía a uno de los graneros (interrumpiendo así todas las conexiones que involucran ese granero). Cuando Bessie hace esto, se rompe la red en trozos más pequeños, cada uno de los cuales retiene conectividad dentro de sí mismo. Para ser lo más disruptivo posible, Bessie quiere asegurarse de que cada una de esas partes se conecte entre sí con no más de la mitad de los graneros de GJ.

Ayude a Bessie a determinar todos los establos que serían adecuados para desconectar.

Entrada

  • Línea 1: Un solo entero, N. Los graneros están numerados 1...N.

  • Líneas 2…N: Cada línea contiene dos números enteros X e Y, que representa una conexión entre los establos X e Y.

Ejemplo de Entrada

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

Detalles de la Entrada

El conjunto de conexiones en la entrada describe un "árbol": conecta todos los graneros juntos y no contiene ciclos.

Salida

  • Líneas 1…?: Cada línea contiene un solo entero, el número (de 1...N) de un establo cuya remoción parte a la red en pedazos, donde cada uno tiene como máximo la mitad del número original de graneros. Los graneros deben mostrarse en la salida en orden numérico creciente. Si no hay graneros adecuados, la salida debe ser una sola línea que contenga la palabra "NONE".

Ejemplo de Salida

3
8

Detalles de la Salida

Si se elimina el granero 3 o el granero 8, la red restante tendrá una pieza compuesta por 5 graneros y dos piezas conteniendo 2 graneros. Si se retira algún otro establo, entonces al menos una de las piezas restantes tiene un tamaño de al menos 6 (que es más de la mitad del número original de graneros, 5).


Comments

There are no comments at the moment.