Solução Imperialismo

Solução de Pedro Michael, comentários de Rogério Júnior

Para ver o problema original, clique aqui.

Observe o pior caso possível: uma a uma, todas as cidades do maior caminho do grafo são conquistadas por uma das cidades das pontas. Neste caso, se o maior caminho tivesse tamanho $$d$$, ele demoraria exatamente $$\big\lceil\frac{d}{2}\big\rceil$$ anos para ser totalmente conquistado. Desse modo, basta descobrirmos o tamanho $$d$$ do maior caminho numa árvore (seu diâmetro) e imprimirmos o valor de $$\big\lceil\frac{d}{2}\big\rceil$$.

Para descobrir o diâmetro de um árvore, escolhemos um vértice qualquer $$v_ori$$ e encontramos seu vizinho mias distante $$v_1$$. Depois, encontramos o vértice $$v_2$$, vizinho mais distante de $$v_1$$, e o caminho de $$v_1$$ a $$v_2$$ é um diâmetro, e tem comprimento $$d$$ máximo.

Segue o código para melhor entendimento:

https://gist.github.com/rogerioagjr/78f545debc41ee609ff774bc8447040e