Submission #1756119

---

Source Code Expand

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)                                                                             
#define seg_size 524288
vector<int> vertexs[200000];
int hukasa[200000] = {};
int findings[200000][100] = {};
int dfs(int now, int back,int deeply) {
	for (int i = 0;i < vertexs[now].size();++i) {
		if (vertexs[now][i] != back) {
			dfs(vertexs[now][i], now, deeply + 1);
		}
	}
	findings[now][1] = back;
	return hukasa[now] = deeply;
}
int dfsing(int now, int back,int deep) {
	int wa = (1 << (deep-1));
	if (wa <= hukasa[now]) {
		int ge = findings[now][deep - 1];
		ge = findings[ge][deep - 1];
		findings[now][deep] = ge;
	}
	for (int i = 0;i < vertexs[now].size();++i) {
		if (vertexs[now][i] != back) {
			dfsing(vertexs[now][i], now,deep);
		}
	}
	return 0;
}
int main() {
	int n;
	cin >> n;
	REP(i, n-1) {
		int a, b;
		cin >> a >> b;
		vertexs[a].push_back(b);
		vertexs[b].push_back(a);
	}
	dfs(1, -1, 0);
	for (int i = 2;i <= 18;++i) {
		dfsing(1, -1, i);
	}
	int query;
	cin >> query;
	for (int i = 0;i < query;++i) {
		int a, b;
		cin >> a >> b;
		if (hukasa[a] > hukasa[b]) swap(a, b);
		int ans = 0;
		while (hukasa[b] - hukasa[a] != 0) {
			int geko = hukasa[b] - hukasa[a];
			for (int i = 1;i >= 0;++i) {
				if ((1 << (i - 1)) > geko) {
					ans += 1 << (i - 2);
					b = findings[b][i - 1];
					break;
				}
			}
		}
		while (a != b) {
			if (findings[a][1] == findings[b][1]) {
				ans += 2;
				break;
			}
			int l = 1, r = 1;
			for (r = 1;r >= 0;++r) {
				if ((1 << r) > hukasa[a]) break;
			}
			r--;
			while (r - l > 1) {
				int m = (l + r) / 2;
				if (findings[a][m] == findings[b][m]) {
					r = m;
				}
				else {
					l = m;
				}
			}
			a = findings[a][l];
			b = findings[b][l];
			ans += 2 * (1 << (l - 1));
		}
		cout << ans+1 << endl;
	}
	return 0;
}

Submission Info

Judge Result