Submission #239922

---

Source Code Expand

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <complex>
#include <cstdio>
using namespace std;

#define REP(i,p,n) for(int i=p;i<n;++i)
#define rep(i,n) REP(i,0,n)

typedef long long int ll;
typedef pair<int,int> pii;
typedef complex<double> point;

const int MAXN = 100001;
const int MAXM = 20;
vector<int> G[MAXN];

int N,Q;
int fs[MAXM][MAXN];
vector<int> ds(MAXN,-2);

void dfs(int index,int parent,int depth)
{
	ds[index] = depth;
	fs[0][index] = parent;

	rep(i,G[index].size()) if(ds[G[index][i]]==-2)
	{
		dfs(G[index][i],index,depth+1);
	}
}

int lca(int a,int b)
{
	if(ds[a]!=ds[b]) // 深さを揃える
	{
		bool ab = ds[a]<ds[b];
		int len = ab ? ds[b]-ds[a] : ds[a]-ds[b];
		int c   = ab ? b : a;
		rep(i,MAXM){ if((len>>i)&1){ c = fs[i][c]; } }
		a = ab ? a : c;
		b = ab ? c : b;
	}

	if( a == b ){ return a; }

	for(int i=MAXM-1;i>=0;--i) if(fs[i][a]!=fs[i][b])
	{
		a = fs[i][a];
		b = fs[i][b];
	}

	return fs[0][a];
}

int main()
{
	cin>>N;
	rep(i,N-1)
	{
		int x,y;
		cin>>x>>y;
		--x;
		--y;

		G[x].push_back(y);
		G[y].push_back(x);
	}

	dfs(0,-1,0);

	rep(i,MAXM-1) rep(j,N)
	{
		fs[i+1][j] = fs[i][j]==-1 ? -1 : fs[i][fs[i][j]];
	}

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

		cout << (ds[a]+ds[b]-2*ds[lca(a,b)]+1) << endl;
	}

	return 0;
}

Submission Info

Judge Result