#include<cstdio>
#include<string.h>
#include<algorithm>
#include<set>
using namespace std;
const int MAXN=10005;
struct edge{
int v,next;
}e[MAXN];
int p[MAXN],eid,d[MAXN],isroot[MAXN];
int f[MAXN][20];
void init(){
memset(p,-1,sizeof(p));
eid=0;
}
void insert(int u,int v){
e[eid].v=v;
e[eid].next=p[u];
p[u]=eid++;
}
set<int>st;
void dfs(int x){
for(int i=p[x];i+1;i=e[i].next){
if(d[e[i].v==-1]){
d[e[i].v]=d[x]+1;
f[e[i].v][0]=x;
dfs(e[i].v);
}
}
return ;
}
int lca(int a,int b){
if(d[a]<d[b]){
swap(a,b);
}
int i,j;
for(i=0;(1<<i)<=d[a];i++);
--i;
for(int j=i;j>=0;j--){
if(d[a]-(1<<j)>=d[b])a=f[a][j];
}
if(a==b)return a;
for(int j=i;j>=0;j--){
if(f[a][j]!=f[b][j]){
a=f[a][j];
b=f[b][j];
}
}
return f[a][0];
}
int main(){
int n;scanf("%d",&n);
init();
for(int i=1;i<n;i++){
int ip1,ip2;
scanf("%d%d",&ip1,&ip2);
isroot[ip2]=1;
insert(ip1,ip2);
}
memset(d,-1,sizeof(d));
int root;
for(int i=1;i<=n;i++){
if(isroot[i]==0){
root=i;break;
}
}
d[root]=0;
dfs(root);
for(int level=1;(1<<level)<=n;level++){
for(int i=1;i<=n;i++){
f[i][level]=f[f[i][level-1]][level-1];
}
}
int p;scanf("%d",&p);
for(int i=1;i<=p;i++){
int ip1,ip2;
scanf("%d%d",&ip1,&ip2);
printf("%d\n",lca(ip1,ip2));
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)