Submission #2522702

---

Source Code Expand

#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define MAX_V 110000
#define MAX_LOG_V 20

vector<int> G[MAX_V];

int parent[MAX_LOG_V][MAX_V]; // 2^k th parent
int depth[MAX_V]; // distance from root
int root = 0;

void dfs(int v, int p, int d){
	parent[0][v] = p;
	depth[v] = d;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] != p){
			dfs(G[v][i], v, d + 1);
		}
	}
}

void init(int V){
	dfs(root, -1, 0);
	for(int k = 0; k < MAX_LOG_V - 1; k++){
		for(int v = 0; v < V; v++){
			if(parent[k][v] < 0){
				parent[k + 1][v] = -1;
			}else{
				parent[k + 1][v] = parent[k][parent[k][v]];
			}
		}
	}
}

int lca(int u, int v){
	if(depth[u] > depth[v]){
		swap(u, v);
	}
	for(int k = 0; k < MAX_LOG_V; k++){
		if((depth[v] - depth[u]) >> k & 1){
			v = parent[k][v];
		}
	}
	if(u == v){
		return u;
	}
	for(int k = MAX_LOG_V - 1; k >= 0; k--){
		if(parent[k][u] != parent[k][v]){
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return u;
}

int main(){
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N - 1; i++){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	init(N);
	
	int Q;
	cin >> Q;
	
	for(int i = 0; i < Q; i++){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		int p = lca(x, y);
		cout << depth[y] - depth[p] - depth[p] + depth[x] + 1 << endl;
	}
	
	return 0;
}

Submission Info

Judge Result