Submission #1609283

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; ++i)
#define FOR(i,n,m) for(long long i=n; i<m; ++i)
#define DUMP(n,a) for(long long dump=0; dump<n; ++dump) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

vector<ll> depth;
vector<vector<ll>> par(21);
void dfs(ll roc,ll d,ll p,vector<vector<ll>>& adj) {
	depth[roc]=d;
	if(p!=-1) par[0][roc]=p;
	REP(i,adj[roc].size()) {
		if(adj[roc][i]==p) continue;
		dfs(adj[roc][i],d+1,roc,adj);
	}
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vector<vector<ll>> adj(n);
	depth.resize(n);
	REP(i,21) par[i].resize(n);
	REP(i,n-1) {
		ll x,y;
		cin>>x>>y;
		--x;--y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	dfs(0,0,-1,adj);
	FOR(i,1,21) {
		REP(j,n) {
			if(depth[j]>=(1<<i)) {
				par[i][j]=par[i-1][par[i-1][j]];
			}
		}
	}
	ll q;
	cin>>q;
	REP(i,q) {
		ll a,b;
		cin>>a>>b;
		--a;--b;
		if(depth[a]<depth[b]) swap(a,b);
		ll lb=-1,ub=depth[b];
		while(ub-lb>1) {
			ll mid=(lb+ub)/2;
			ll _a=a;
			ll _b=b;
			int c=0;
			for(ll ca=depth[a]-depth[b]+mid; ca>0; ca/=2) {
				if(ca%2==1) _a=par[c][_a];
				++c;
			}
			c=0;
			for(ll cb=mid; cb>0; cb/=2) {
				if(cb%2==1) _b=par[c][_b];
				++c;
			}
			if(_a!=_b) lb=mid;
			else ub=mid;
		}
		++lb;
		cout<<(2*lb+(depth[a]-depth[b]))+1<<endl;
	}
}

Submission Info

Judge Result