Submission #4047882

---

Source Code Expand

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

using namespace std;

class LCA {
	vector<vector<int>> G, parent;
	vector<int> depth;
	size_t MAX_LOG_V;

	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); }
		}
	}

public:
	LCA(const vector<vector<int>>& g) : G(g) {
		size_t V = g.size();
		MAX_LOG_V = 0;
		while (pow(2, MAX_LOG_V) <= V) { ++MAX_LOG_V; }
		parent = vector<vector<int>>(MAX_LOG_V, vector<int>(V));
		depth = vector<int>(V);
		dfs(0, -1, 0);
		for (int k = 0; k + 1 < MAX_LOG_V; ++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 parent[0][u];
	}

	int dist(int u, int v) {
		return (depth[u] + depth[v] - 2 * depth[lca(u, v)]);
	}
};

int main() {
	int N;
	cin >> N;
	vector<vector<int>> G(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);
	}
	int Q;
	cin >> Q;
	vector<int> a(Q);
	vector<int> b(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	LCA lca(G);
	for (int i = 0; i < Q; ++i) {
		int res = lca.dist(a[i], b[i]) + 1;
		cout << res << endl;
	}

	return 0;
}

Submission Info

Judge Result