São João

saojoao.cpp

// São João - Seletiva IOI 2014
// Rogério Júnior
// Complexidade: O(v)

#include <vector> // vector
#include <cstdio> // scanf e printf

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

#define PB push_back // por comodidade

#define MAXN 100100 // defino o valor de MAXN


// declaro as variáveis que vou usar
int n, v, d1, d2, dist[3][MAXN];

// salvarei o grafo em uma lista de adjacências
vector<int> lista[MAXN];

// primeira DFS
void dfs1(int u){
	
	// para cada vizinho p de u
	for(int i=0; i<lista[u].size(); i++){
		
		int p=lista[u][i];
		
		// se o já tiver visitado (ele for pai de u)
		// vou para a próxima iteração do for
		if(dist[0][p]>0) continue;
		
		// a distância da origem a p
		// é a distância da origem a u, somada de 1
		dist[0][p]=dist[0][u]+1;
		
		// lembro de guardar o vértice mais distante da origem
		if(dist[0][p]>dist[0][d1]) d1=p;
		
		// e chamo a DFS em p
		dfs1(p);
	}
}

// segunda DFS
void dfs2(int u){
	
	for(int i=0; i<lista[u].size(); i++){
		
		int p=lista[u][i];
		
		if(dist[1][p]>0) continue;
		
		dist[1][p]=dist[1][u]+1;
		
		if(dist[1][p]>dist[1][d2]) d2=p;
		
		dfs2(p);
	}
}

// terceira DFS
void dfs3(int u){
	
	for(int i=0; i<lista[u].size(); i++){
		
		int p=lista[u][i];
		
		if(dist[2][p]>0) continue;
		
		dist[2][p]=dist[2][u]+1;
		
		dfs3(p);
	}
}

int main(){
	
	// leio o valor de n
	scanf("%d", &n);
	
	// para cada aresta
	for(int i=1; i<n; i++){
		
		// leio os vértices que a ligam
		int p, q;
		scanf("%d %d", &p, &q);
		
		// e adiciono a aresta na lista de adjacências
		lista[p].PB(q);
		lista[q].PB(p);
	}
	
	// o vértice 1 será a origem da primeira DFS
	// logo dist[0][1] será zero
	dist[0][1]=0;
	
	// chamo a DFS em 1
	dfs1(1);
	
	// faço a DFS na primeira ponta do diâmetro
	dist[1][d1]=0;
	dfs2(d1);
	
	// e depois na segunda ponta
	dist[2][d2]=0;
	dfs3(d2);
	
	// agora tenho as distância de quaisquer vértices
	// a qualquer uma das pontas do diâmetro
	
	// leio a quantidade de queries
	scanf("%d", &v);
	
	// para cada query
	for(int i=1; i<=v; i++){
		
		// leio os valores de a e m
		int a, m;
		scanf("%d %d", &a, &m);
		
		// vejo qual ponta do diâmetro está mais distante de a
		int maior=max(dist[1][a],dist[2][a]);
		
		// e imprimo a resposta
		printf("%d\n", min(n, min(m+1, maior+1) + max(0, (m-maior)/2)));
	}
	
	return 0;
}