Encontrar o centróide de uma árvore
Recebe-se uma árvore com v vértices e o objetivo é identificar o centróide dessa árvore. O centróide de uma árvore é um vértice cuja remoção garante que todos os subárvores remanescentes tenham, no máximo, nós.
Entrada
A primeira linha da entrada contém um único inteiro v (1 ≤ v ≤ 100 000).
As seguintes v-1 linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), o que significa que o vértice v1 está ligado ao vértice v2 e vice-versa.
Saída
O programa deve imprimir o centróide da árvore dada. Se houver várias respostas possíveis, o programa pode imprimir qualquer uma delas.
Exemplos
Entrada | Saída |
|---|---|
3 1 2 1 3 | 1 |
5 1 2 2 3 3 4 3 5 | 3 |
Dica
Pode calcular o tamanho de cada subárvore (isto é, quantos nós filhos ela contém).
Depois, verifique para todos os subárvores de cada nó se o tamanho de cada uma delas é menor ou igual a metade do número total de vértices da árvore (some também v-currentNodeSize para considerar a parte da árvore acima do nó atual).
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB