Submission #1869447

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N, Q;
vector<vector<int>> G;
int par[18][100000];
int deg[100000];
int maxDeg;
void dfs(int n, int p, int d) {
	maxDeg = max(maxDeg, d);
	par[0][n] = p;
	for (int s = 0; s < G[n].size(); ++s) {
		int child = G[n][s];
		if (child == n) continue;
		dfs(child, n, d + 1);
	}
}
void doubling(){
	for (int k = 1; k <= ceil(log2(maxDeg)); ++k) {
		for (int n = 0; n < N; ++n) {
			if (par[k - 1][n] == -1) par[k][n] = -1;
			else par[k][n] = par[k - 1][par[k - 1][n]];
		}
	}
}
int lca(int a, int b) {
	if (deg[b] < deg[a]) swap(a, b);
	int m = deg[b] - deg[a];
	for (int i = 0; i < floor(log2(m)) + 1; ++i) {
		if (m & (1U << i)) {
			b = par[i][b];
		}
	}
	if (a == b) return a;
	for (int k = ceil(log2(maxDeg)); k >= 0; --k) {
		if (par[k][a] >= 0 && par[k][a] == par[k][b]) break;
		a = par[k][a];
		b = par[k][b];
	}
	return par[0][a];
}
int main(void) {
	cin >> N >> Q;
	G.resize(N);
	for (int n = 0; n < N; ++n) {
		int a, b; cin >> a >> b;
		--a; --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int root = 0;
	dfs(root, -1, 0);
	doubling();
	cin >> Q;
	for (int q = 0; q < Q; ++q) {
		int a, b; cin >> a >> b;
		--a; --b;
		int l = lca(a, b);
		cout << deg[a] + deg[b] - deg[l] - deg[l] + 1 << endl;
	}
	return 0;
}

Submission Info

Judge Result