BALENCIAGA • 3个月前
using namespace std; const int N=1e5+10; int t[N],f[N][30],head[N],ne[N],to[N],h[N]; int n,m,cnt,rt; void add(int x,int y) {
to[cnt]=y;
ne[cnt]=head[x];
head[x]=cnt++;
} void dfs(int x,int fa) {
h[x]=h[fa]+1;//儿子的深度是父亲的深度+1
f[x][0]=fa;//x的直接祖先是fa
for(int i=1; (1<<i)<=h[x]; i++)
f[x][i]=f[f[x][i-1]][i-1];//RMQ原理,f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
for(int i=head[x]; ~i; i=ne[i])//
{
if(to[i]==fa)
continue;
// f[to[i]][0]=x;
dfs(to[i],x);
}
} int lca(int x,int y) {
if(h[x]<h[y]) swap(x,y);//使x是大高度
for(int i=20;i>=0;i--)//把x和y变为同一高度
{
if(h[f[x][i]]>=h[y])
x=f[x][i];
if(x==y)//如果x==y,说明x是祖先
return x;
}
for(int i=20; i>=0; i--)//x,y一起向上跳,直到重合的下一个深度
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];//此时上一深度,即为共同祖先
} int main() {
int a,b,i,j,k;
scanf("%d",&n);
rt=0;
memset(head,-1,sizeof(head));
for(i=0; i<n; i++)
{
scanf("%d%d",&a,&b);
if(b==-1)
rt=a;
else
add(a,b),
add(b,a);
}
f[rt][0]=rt;//
dfs(rt,-1);
/*for(i=1; i<=21; i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);*/
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&a,&b);
int p=lca(a,b);
if(p==a)
printf("1\n");
else if(p==b)
printf("2\n");
else
printf("0\n");
}
return 0;
}
评论:
请先登录,才能进行评论