Submission #230655

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <list>

#define INF 100000000
#define FOR(i, a, b) for (int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef list<pii>::iterator lpite;
const double PI = acos(-1.0);

vector<int> G[100001];
int root = 0;

int parent[30][100001];
int depth[100001];

int N, Q;

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

void init(int V)
{
	dfs(root, -1, 0);
	FOR(k, 0, 30-1) {
		FOR(v, 0, 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(k, 0, 30-1) {
		if ( (depth[v]-depth[u]) >> k & 1 ) {
			v = parent[k][v];
		}
	}
	if (u==v) return u;
	for (int k = 30-1; k >= 0; k--) {
		if (parent[k][u] != parent[k][v]) {
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

int main()
{
	ios::sync_with_stdio(false);

	cin >> N;
	FOR(i,0,N-1){
		int x,y;
		cin >> x >> y;
		x--, y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	init(N);

	cin >> Q;
	while (Q--) {
		int a,b;
		cin >> a >> b;
		a--, b--;
		int p = lca(a, b);
		cout << depth[a]+depth[b]-2*depth[p] + 1<< "\n";
	}

	return 0;
}

Submission Info

Judge Result