Submission #230430

---

Source Code Expand

#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
struct edge { int u, v; ll w; int rev; };

vector<int> G[100000];
int parent[20][100000];
int depth[100000];

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(0, -1, 0);
	for (int k = 0; k + 1 < 20; 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 < 20; k++)
		if ((depth[v] - depth[u]) >> k & 1)
			v = parent[k][v];
	if (u == v) return u;
	for (int k = 20 - 1; 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;
	for (int i = 0; i < N - 1; i++) {
		int x, y; cin >> x >> y;
		G[x - 1].push_back(y - 1);
		G[y - 1].push_back(x - 1);
	}
	init(N);
	int Q; cin >> Q;
	for (; Q > 0; Q--) {
		int a, b; cin >> a >> b;
		a--; b--;
		cout << depth[a] + depth[b] - depth[lca(a, b)] * 2 + 1 << endl;
	}
}

Submission Info

Judge Result