祖孙询问（LCA）

祖孙询问（LCA）

已知一棵 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。

样例
Input
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

Output
1
0
0
0
2

数据范围与提示
对于 30% 的数据，1≤n,m≤10³；

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

思路： LCA板

AC代码：

#include
#include
#include
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;//儿子的深度是父亲的深度+1f[x][0]=fa;//x的直接祖先是fafor(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;elseadd(a,b),add(b,a);}f[rt][0]=rt;//dfs(rt,-1);/*for(i=1; i<=21; i++)lg[i]=lg[i-1]+(1<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");elseprintf("0\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！