首页 > 代码库 > 洛谷 P3379 【模板】最近公共祖先（LCA） 题解
洛谷 P3379 【模板】最近公共祖先（LCA） 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.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。
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 5 const int INF = 0x3f3f3f3f; 6 const int MAXN = 500000 + 10; 7 const int MAXE = 500000 + 10; 8 9 inline void read(int &x) 10 { 11 x = 0;char ch = getchar();char c = ch; 12 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 13 while(ch <= ‘9‘ && ch >= ‘0‘)x = (x<<1) + (x<<3) + ch - ‘0‘, ch = getchar(); 14 if(c == ‘-‘)x = -x; 15 } 16 17 inline void swap(int &a,int &b) 18 { 19 int tmp = a; 20 a = b; 21 b = tmp; 22 } 23 24 struct Edge 25 { 26 int u,v,nxt; 27 }edge[MAXE << 1]; 28 29 int head[MAXN],cnt,n,m,root; 30 31 void insert(int a,int b) 32 { 33 edge[++ cnt] = (Edge){a,b,head[a]}; 34 head[a] = cnt; 35 } 36 37 int tmp1,tmp2; 38 int vis[MAXN],f[MAXN][21],deep[MAXN]; 39 40 void dfs(int u,int step) 41 { 42 for(int pos = head[u];pos;pos = edge[pos].nxt) 43 { 44 int v = edge[pos].v; 45 if(!vis[v]) 46 { 47 vis[v] = 1; 48 deep[v] = step+1; 49 f[v][0] = u; 50 dfs(v,step+1); 51 } 52 } 53 } 54 55 void init() 56 { 57 vis[root] = true; 58 deep[0] = 0; 59 dfs(root,0); 60 for(int j = 1;(1<<j) <= n;++ j) 61 for(int i = 1;i <= n;++ i) 62 f[i][j] = f[f[i][j-1]][j-1]; 63 } 64 65 int lca(int va,int vb) 66 { 67 if(deep[va] < deep[vb]) swap(va,vb); 68 int M = 0; 69 for(;(1<<M) <= n;++ M); 70 M --; 71 for(int i = M;i >= 0;-- i) 72 if(deep[va] - (1<<i) >= deep[vb]) 73 va = f[va][i]; 74 if(va == vb) return va; 75 for(int j = M;j >= 0;-- j) 76 { 77 if(f[va][j] != f[vb][j]) 78 { 79 va = f[va][j]; 80 vb = f[vb][j]; 81 } 82 } 83 return f[va][0]; 84 } 85 86 int main() 87 { 88 read(n);read(m);read(root); 89 for(int i = 1;i < n;++ i) 90 { 91 read(tmp1);read(tmp2); 92 insert(tmp1,tmp2); 93 insert(tmp2,tmp1); 94 } 95 init(); 96 for(int i = 1;i <= m;++ i) 97 { 98 read(tmp1);read(tmp2); 99 printf("%d\n",lca(tmp1,tmp2));100 }101 return 0;102 }
洛谷 P3379 【模板】最近公共祖先（LCA） 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。