【洛谷_P3379】【模板】最近公共祖先（LCA）

本文主要是介绍【洛谷_P3379】【模板】最近公共祖先（LCA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N-1 行每行包含两个正整数 x, yx,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 M 行每行包含两个正整数 a, b，表示询问 a 结点和 b 结点的最近公共祖先。

输出格式

输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例

输入 #1

输出 #1

解题思路

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;
}