Submission #4047623

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<vector<int>> G;
int root;

int parent[18][100010];
int depth[100010];

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 + 1 < 18; ++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 < 18; ++k) {
		if ((depth[v] - depth[u])>>k & 1) {
			v = parent[k][v];
		}
	}
	if (u == v) { return u; }
	
	for (int k = 17; k >= 0; --k) {
		if (parent[k][u] != parent[k][v]) {
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

int main() {
	int N;
	cin >> N;
	G.resize(N + 1);
	for (int i = 0; i < N - 1; ++i) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int Q;
	cin >> Q;
	vector<int> a(Q);
	vector<int> b(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> a[i] >> b[i];
	}

	root = 1;
	init(N);
	for (int i = 0; i < Q; ++i) {
		int p = lca(a[i], b[i]);
		int res = (depth[a[i]] - depth[p]) + (depth[b[i]] - depth[p]) + 1;
		cout << res << endl;
	}

	return 0;
}

Submission Info

Judge Result