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;
	}

view raw

imperialismo_pedro.cpp

hosted with ❤ by GitHub