Submission #1869341

---

Source Code Expand

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, Q;
int deg[100000];
int par[100000];
vector<vector<int>> child;
int lca(int a, int b) {
	if (deg[b] < deg[a]) swap(a, b);
	while (deg[b] - deg[a] > 0) b = par[b];
	if (a == b) return a;
	while (a != b) {
		a = par[a];
		b = par[b];
	}
	return a;
}
int main(void) {
	cin >> N;
	child.resize(N);
	for (int n = 0; n < (N - 1); ++n) {
		int a, b; cin >> a >> b;
		--a; --b;
		child[a].push_back(b);
		child[b].push_back(a);
	}
	int root = 0;
	par[root] = -1;
	queue<pair<int, int>> q; q.emplace(root, 0);
	while (!q.empty()) {
		pair<int, int> p = q.front(); q.pop();
		int id = p.first;
		int d = p.second;
		for (int s = 0; s < child[id].size(); ++s) {
			int c = child[id][s];
			if (c == par[id]) continue;
			deg[c] = d + 1;
			par[c] = id;
			q.emplace(c, deg[c]);
		}
	}
#ifdef LOCAL
	cin >> Q;
	vector<pair<int, int>> v;
	for (int i = 0; i < Q; ++i) {
		int a, b; cin >> a >> b;
		--a; --b;
		v.emplace_back(a, b);
	}
	for (int s = 0; s < v.size(); ++s) {
		pair<int, int> p = v[s];
		int a = p.first;
		int b = p.second;
		int l = lca(a, b);
		cout << deg[a] + deg[b] - (deg[l] * 2) + 1 << endl;
	}
#else
	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		int a, b; cin >> a >> b;
		--a; --b;
		int l = lca(a, b);
		cout << deg[a] + deg[b] - (deg[l] * 2) + 1 << endl;
	}
#endif
	return 0;
}

Submission Info

Judge Result