Finding a Centroid.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Dado un árbol de $n$ ~n~ nodos, su tarea es encontrar un centroide, es decir, un nodo tal que, al designarlo como raíz del árbol, cada subárbol tenga como máximo $\lfloor n/2 \rfloor$ ~\lfloor n/2 \rfloor~ nodos.

Entrada

La primera línea de entrada contiene un entero $n$ ~n~: el número de nodos. Los nodos están numerados del $1$ ~1~ al $n$ ~n~. A continuación, hay $n-1$ ~n-1~ líneas que describen las aristas. Cada línea contiene dos enteros $a$ ~a~ y $b$ ~b~: existe una arista entre los nodos $a$ ~a~ y $b$ ~b~.

Salida

Imprima un entero: el nodo centroide.

Restricciones

$1 \leq n \leq 2 \cdot 10^5$ ~1 \leq n \leq 2 \cdot 10^5~
$1 \leq a,b \leq n$ ~1 \leq a,b \leq n~

Ejemplo de Entrada

Ejemplo de Salida

Comments

0

_Durios commented on March 28, 2026, 2:27 p.m.

En este problema si encuentro dos centroides, cual de ellos debo imprimir?