【洛谷_P3379】【模板】最近公共祖先(LCA)
程序员文章站
2022-06-22 23:45:28
【模板】最近公共祖先(LCA)题目描述如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。输入格式第一行包含三个正整数 N,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。接下来 N-1 行每行包含两个正整数 x, yx,y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以构成树)。接下来 M 行每行包含两个正整数 a, b,表示询问 a 结点和 b 结点的最近公共祖先。输出格式输出包含 M 行,每行包含一个正整数,依次为每一个询问的结果。输入输出样例...
【模板】最近公共祖先(LCA)
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1 行每行包含两个正整数 x, yx,y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 M 行每行包含两个正整数 a, b,表示询问 a 结点和 b 结点的最近公共祖先。
输出格式
输出包含 M 行,每行包含一个正整数,依次为每一个询问的结果。
输入输出样例
输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出 #1
4
4
1
4
4
解题思路
LCA模板题,不解释
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,s;
int tot,hd[5000010];
int dep[5000010],f[5000010][20];
struct abc{
int to,next;
}b[5000010];
void add(int x,int y)
{
b[++tot]=(abc){y,hd[x]};
hd[x]=tot;
}
int lca(int x,int y)
{
if(dep[x]>dep[y])
swap(x,y);
int cnt=dep[y]-dep[x],k=19,t=1<<k;
while(cnt)
{
if(cnt>=t)
y=f[y][k],cnt-=t;
k--;
t/=2;
}
if(x==y) return x;
k=19;
while(k>=0)
{
if(f[x][k]!=f[y][k])
{
x=f[x][k];
y=f[y][k];
}
k--;
}
return f[x][0];
}
void dfs(int x,int fa)
{
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(int i=hd[x];i;i=b[i].next)
{
int y=b[i].to;
if(y==fa)
continue;
dfs(y,x);
}
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(s,0);
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
cout<<lca(x,y)<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/SSL_guyixin/article/details/108170793