Capitais

capitais.cpp

// Capitais - F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(n log n)

#include <cstdio> // scanf e printf
#include <vector> // vector
#include <algorithm> // função min

using namespace std; // para uso do C++

// definoos valores de INF e MAXN
#define MAXN 100100
#define INF 0x3f3f3f3f

// defino PB como push_back
#define PB push_back

// declaro as variáveis que vou usar
vector<int> lista[MAXN], ord;

int n, pai[MAXN], lvl[MAXN], menor[MAXN], resp=INF;

// DFS para montar a árvore
int dfs(int v=1){ // partindo do vértice V para baixo
	
	// para cada vizinho de v
	for(int i=0; i<lista[v].size(); i++){
		
		// seja U o vizinho que estou explorando
		int u=lista[v][i];
		
		// se ele já tiver sido explorado, continuo
		if(pai[u]) continue;
		
		// caso contrário
		
		// o pai de U é V
		pai[u]=v; 
		
		// e, portanto, seu nível é o nível de V mais 1
		lvl[u]=lvl[v]+1;
		
		// e chamo a DFS em U
		dfs(u);
	}
}

// função para ordenação dos vértices por nível
bool cmp(int x, int y){
	
	return lvl[x] > lvl[y];
}

int main(){
	
	// leio o valor de n
	scanf("%d", &n);
	
	// leio a árvore da entrada
	for(int i=1; i<n; i++){
		
		int v, u;
		scanf("%d %d", &v, &u);
		
		lista[v].PB(u);
		lista[u].PB(v);
	}
	
	// defino 1 como pai de si mesmo
	pai[1]=1;
	
	// e chamo a DFS tendo 1 como raiz da árvore
	dfs();
	
	// preecho o vetor ord com o vértices de 1 a n
	for(int i=1; i<=n; i++) ord.PB(i);
	
	// ordeno o vetor pelo nível dos vértices
	sort(ord.begin(), ord.end(), cmp);
	
	// percorro  vetor ordendo
	for(int i=0; i<ord.size()-1; i++){
		
		// v é o vértice atual e p é seu pai
		int v=ord[i], p=pai[v];
		
		// se menor[v] ainda é zero, ele não tem filhos e é capital
		// logo a capital mais alta que descende de v é ele mesmo
		if(!menor[v]) menor[v]=lvl[v];
		
		// se menor[p] ainda é zero
		// então não processamos nenhum outro filho de p
		if(!menor[p]){
			
			// logo o menor[p] será menor[v]
			menor[p]=menor[v];
			
			// e continuo para o próximo vértice
			continue;
		}
		
		// se menor[p] não for zero, vemos se a distância do descendente mais alto de v
		// para o mais alto de p é menor que a resposta que temos até agora
		
		// se for, essa será a nova resposta
		resp=min(resp, menor[p]+menor[v]-2*lvl[p]);
		
		// por fim, vemos se a capital descendente mais alta de v é mais alta
		//	que a mais alta de p encontrada até agora
		
		// se for, ele será o novo descendente mais alto de p
		menor[p]=min(menor[p], menor[v]);
	}
	
	// se a raiz (1) for capital (tiver um único vizinho)
	if(lista[1].size()==1)
		
		// percorremos todo o grafo
		for(int v=2; v<=n; v++)
			
			// para cada capital, se a sua distância para a raiz (seu nível)
			// for menor que a resposta, essa distância será a nova resposta
			if(lista[v].size()==1) resp=min(resp, lvl[v]);
	
	// por fim, imprimo o valor salvo em resp
	printf("%d\n", resp);
	
	return 0;
}