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:


#include <stdio.h>
#include <vector>
#include <string.h>
#define MAX 100001
using namespace std;
vector<int> grafo[MAX];
int vis[MAX], v, d;
void dfs(int u, int dist)
{
vis[u]=1;
// se encontrei o mais distante, atualizo
if(dist > d)
d = dist, v = u;
// para cada vizinho de u
for(int i = 0; i < grafo[u].size(); i++)
{
// chamo a DFS nos ainda não explorados
int no = grafo[u][i];
if(!vis[no])
dfs(no, dist+1);
}
}
int main()
{
int n, pi;
while(scanf("%d", &n) && n != -1)
{
for(int i = 1; i <= n; i++)
vis[i] = 0, grafo[i].clear();
// leio o grafo
for(int i = 2; i <= n; i++)
{
scanf("%d", &pi);
grafo[pi].push_back(i);
grafo[i].push_back(pi);
}
// através de DFS em árvores
// encontro o vizinho mais distante de 1, v
d=0;
dfs(1, 0);
for(int i = 1; i <= n; i++)
vis[i] = 0;
// e a distância para o vizinho mais distante de v
d=0;
dfs(v, 0);
// e imprimo a resposta
printf("%d\n", (d+1) / 2);
}
return 0;
}