首页 > 代码库 > 洛谷——P3379 【模板】最近公共祖先（LCA）
洛谷——P3379 【模板】最近公共祖先（LCA）
https://www.luogu.org/problem/show?pid=3379#sub
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：
第一行包含三个正整数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。
1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4 5 #define N 500005 6 7 using namespace std; 8 9 char ch;10 int n,a,b,m,s,y,cnt;11 vector<int>que[N];12 int head[N],qa[N],qb[N],fa[N],dad[N],ans[N];13 struct TypeEdge14 {15 int to,next;16 }edge[N*2];//无向图开两倍 17 18 void add(int x,int y)19 {20 cnt++;21 edge[cnt].next=head[x];22 edge[cnt].to=y;23 head[x]=cnt;24 }25 26 void read(int &x)27 {28 x=0; ch=getchar();29 while(ch<‘0‘||ch>‘9‘) ch=getchar();30 while(ch>=‘0‘&&ch<=‘9‘)31 {32 x=x*10+ch-‘0‘;33 ch=getchar();34 }35 } 36 37 int find(int x)38 {39 return x==fa[x]?x:fa[x]=find(fa[x]);40 }41 42 void DFS(int x)43 {44 fa[x]=x;45 for(int i=head[x];i;i=edge[i].next)46 if(dad[x]!=edge[i].to) dad[edge[i].to]=x,DFS(edge[i].to);47 for(int i=0;i<que[x].size();i++)48 if(dad[y=qa[que[x][i]]^qb[que[x][i]]^x]) ans[que[x][i]]=find(y);49 fa[x]=dad[x];50 }51 52 int main()53 {54 read(n);read(m);read(s);55 for(int i=1;i<n;i++)56 {57 read(a);read(b);58 add(a,b);add(b,a);59 }60 for(int i=1;i<=m;i++)61 {62 read(qa[i]);read(qb[i]);63 que[qa[i]].push_back(i);64 que[qb[i]].push_back(i);65 }66 DFS(s);67 for(int i=1;i<=m;i++)68 printf("%d\n",ans[i]);69 return 0;70 }
洛谷——P3379 【模板】最近公共祖先（LCA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。