Submission #2209883

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int pa[100005][20];//parent //place, 2^i parent
vector<int> path[100005];
vector<int> his;//history
bool used[100005];
int deep[100005];
int s[100005];


void make_tree(int t){
	int a;
	int i,j,k;
	used[t]=true;
	deep[t]=his.size();
	his.push_back(t);
	for(i=0;;i++){
		j=his.size()-(1<<i)-1;
		if(j<0)break;
		pa[t][i]=his[j];
	}
	for(i=0;i<path[t].size();i++){
		a=path[t][i];
		if(used[a])continue;
		make_tree(a);
	}
	his.pop_back();
}

int check(int a,int b){
	int i,j,k;
	int s=0;
	if(deep[a]<deep[b])swap(a,b);
	k=deep[a]-deep[b];
	for(i=0;k>0;i++){
		if((k&(1<<i))!=0){
			k-=(1<<i);
			a=pa[a][i];
		}
	}
	k=deep[a];
	for(j=0;k>=(1<<j);j++){}
	j--;
	for(i=j;i>=0;i--){
		if(pa[a][i]!=pa[b][i])a=pa[a][i],b=pa[b][i];
	}
	if(a==b)s=a;
	else s=pa[a][0];
	return s;
}

int main(){
	int n,m;
	int i,j,k;
	int a,b;
	memset(pa,-1,sizeof(pa));
	cin>>n;
	for(i=0;i<n-1;i++){
		cin>>a>>b;
		a--,b--;
		path[a].push_back(b);
		path[b].push_back(a);
	}
	make_tree(0);
	cin>>m;
	for(i=0;i<m;i++){
		cin>>a>>b;
		a--,b--;
		s[i]=deep[a]+deep[b]-2*deep[check(a,b)]+1;
	}
	for(i=0;i<m;i++){
		cout<<s[i]<<endl;
	}
	return 0;
}
	

Submission Info

Judge Result