首页 > 代码库 > 最近公共祖先（LCA）问题的树剖实现 （模板）
最近公共祖先（LCA）问题的树剖实现 （模板）
我来存个档，防止忘记！2333
传送门：https://daniu.luogu.org/problem/show?pid=3379
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式：
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例
输入样例#1：
5 5 43 12 45 11 42 43 23 51 24 5
输出样例#1：
44144
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
该树结构如下：
第一次询问：2、4的最近公共祖先，故为4。
第二次询问：3、2的最近公共祖先，故为4。
第三次询问：3、5的最近公共祖先，故为1。
第四次询问：1、2的最近公共祖先，故为4。
第五次询问：4、5的最近公共祖先，故为4。
故输出依次为4、4、1、4、4。
一些定义：
- 重孩子：儿子节点所有孩子中size最大的；
- 轻孩子：儿子节点中除了重儿子的；
- 重边：连接重儿子的边；
- 轻边：连接轻儿子的边；
- 重链：重边连成的链；
轻链：轻边连成的链；
思想：树剖LCA是让当前两个节点所在链首深度大的走到链首的父节点直到在一条重链上，返回深度小的节点即为LCA。
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int n,m,s,cnt,x,y;struct sdt{ int to,nxt;}a[1000005];int head[500005],top[500005],deep[500005],par[500005],son[500005],num[500005];int read(){ int x=0;char c=getchar(); while(c<48||c>57)c=getchar(); while(c>47&&c<58)x*=10,x+=c-48,c=getchar(); return x;}void add(int fr,int tox){ a[++cnt].to=tox; a[cnt].nxt=head[fr]; head[fr]=cnt;}void build(int x){ deep[x]=deep[par[x]]+1; num[x]=1; for(int i=head[x];i;i=a[i].nxt) { int y=a[i].to; if(par[x]!=y && !par[y]) { par[y]=x; build(y); num[x]+=num[y]; if(num[y]>num[son[x]])son[x]=y; } }}void find(int x){ if(son[x])top[son[x]]=top[x]; else return ; for(int i=head[x];i;i=a[i].nxt) { int y=a[i].to; if(par[y]==x) { if(y!=son[x])top[y]=y; find(y); } }}int query(int x,int y){ if(top[x]==top[y]) { if(deep[x]<deep[y])return x; else return y; } if(deep[top[x]]<deep[top[y]])y=par[top[y]]; else x=par[top[x]]; return query(x,y);}int main(){ n=read();m=read();s=read(); for(int i=1;i<=n-1;i++) { x=read();y=read(); add(x,y); add(y,x); } deep[0]=-1; build(s); top[s]=s; find(s); for(int i=1;i<=m;i++) { x=read();y=read(); printf("%d\n",query(x,y)); } return 0;}
最近公共祖先（LCA）问题的树剖实现 （模板）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。