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