Finding a Centroid.

Submit solution
Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M
Author:
FrankHG
Problem type

Dado un árbol de 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 nodos.

Entrada

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

Salida

Imprima un entero: el nodo centroide.

Restricciones

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

Ejemplo de Entrada

5
1 2
2 3
3 4
3 5

Ejemplo de Salida

3

Comments


  • 0
    Luisito0101  commented on April 4, 2026, 8:57 p.m.

    lo que pasa con este problema, es que es sacado del CSES y en el CSES dice que si hay varias posibilidades, puedes imprimir cualquiera. Deberían aclarar eso para este problema. (btw, también lo hice con dfs y me da WA dos casos (el AC fue por poner dos parches))


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

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


    • -3
      romelio_suarez  commented on April 3, 2026, 9:24 p.m. ← edit 2

      sencillo: si despues del dfs encuentras que para los vecinos u existe algun nodo que satisfaga que el subarbol[vecino] > N/2 entonces te mueves hacia ese vecino y si hay algun centroide por ahi agarras ese, asi fue como me resulto. O sea usas primero el dfs para calcular el tama;o de cada componente y luego usas backtracking para encontrar el centroide