「4.4」祖孙询问

 

「4.4」祖孙询问

题目描述

已知一棵 n 个节点的有根树。有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 n 表示节点个数；
接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 -1，那么 a 就是树的根；
第 n+2 行是一个整数 m 表示询问个数；
接下来 m 行，每行两个正整数 x 和 y，表示一个询问。

输出格式

对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

样例输入1

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

样例输出1

1
0
0
0
2

注释说明

对于 30% 的数据，1≤n,m≤10^3；
对于 100% 的数据，1≤n,m≤4×10^4，每个节点的编号都不超过 4×10^4。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,pre[N],f[N][17],dep[N],k,lg[N];
struct node{int to,next;
}e[N*2];
void add(int u,int v){e[++k]=(node){v,pre[u]};pre[u]=k;
}
void dfs(int x,int fa){f[x][0]=fa;dep[x]=dep[fa]+1;for(int i=pre[x];i!=0;i=e[i].next){int to=e[i].to;if(to==fa)continue;dfs(to,x);}
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]];if(x==y)return x;for(int i=16;i>=0;i--){if(f[x][i]!=f[y][i]){//printf("(%d,%d)",f[x][i],f[y][i]);x=f[x][i];y=f[y][i];}}return f[x][0];
}
int main(){scanf("%d",&n);int rt,x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(y==-1){rt=x;continue;}add(x,y);add(y,x);}dfs(rt,0);for(int i=2;i<=N;i++)lg[i]=lg[i/2]+1;for(int j=1;j<=16;j++){for(int i=1;i<=N;i++){f[i][j]=f[f[i][j-1]][j-1];}}int m;scanf("%d",&m);while(m--){scanf("%d%d",&x,&y);int lc=lca(x,y);//printf("%d\n",lc);if(lc==x)puts("1");else if(lc==y)puts("2");else puts("0");}
}
/*
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 234
234 17
233 13
233 15
233 19
*/