Submission #3629067

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

vector<int> E[100001];
int P[20][100001];
int D[100001];

int oya(int A, int B) {
	if (B == 0) return A;
	int kazu = 0;
	int kari = B;
	while (kari > 1) {
		kazu++;
		kari /= 2;
	}
	return oya(P[kazu][A], B - (1 << kazu));
}

void dfs(int A, int B, int C) {
	if (D[A] == 0) {
		D[A] = B;
		P[0][A] = C;
		int mae = C;
		rep(i, 19) {
			P[i + 1][A] = oya(mae, 1 << i);
			mae = P[i + 1][A];
		}
		for (int i : E[A]) dfs(i, B + 1, A);
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N;
	cin >> N;
	rep(i, N - 1) {
		int x, y;
		cin >> x >> y;
		E[x].pb(y);
		E[y].pb(x);
	}

	dfs(1, 1, 0);

	int Q;
	cin >> Q;
	rep(i, Q) {
		int a, b;
		cin >> a >> b;

		if (D[a] > D[b]) swap(a, b);
		int sa = D[b] - D[a];
		b = oya(b, sa);

		int L = 0;
		int R = D[a];
		while (L < R) {
			int half = (L + R) / 2;
			if (oya(a, half) == oya(b, half)) R = half;
			else L = half + 1;
		}
		co(L * 2 + sa + 1);
	}

	Would you please return 0;
}

Submission Info

Judge Result