Submission #1575202

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, q;
int par[20][100005], dep[100005];
vector<int> g[100005];

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

void init() {
	dfs(0, -1, 0);
	FOR(k, 20-1) {
		FOR(v, n) {
			if (par[k][v] < 0) par[k+1][v] = -1;
			else par[k+1][v] = par[k][par[k][v]];
		}
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	FOR(k, 20) {
		if ((dep[v]-dep[u]) >> k & 1) {
			v = par[k][v];
		}
	}
	if (u == v) return u;
	for (int k = 20-1; k >= 0; k--) {
		if (par[k][u] != par[k][v]) {
			u = par[k][u];
			v = par[k][v];
		}
	}
	return par[0][u];
}

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n;
	FOR(i, n-1) {
		int a, b;
		cin >> a >> b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	init();
	cin >> q;
	vector<int> ans(q);
	FOR(i, q) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		ans[i] = dep[a] + dep[b] - 2 * dep[lca(a, b)] + 1;
	}
	FOR(i, q) cout << ans[i] << endl;
	return 0;
}

Submission Info

Judge Result