首页 > 代码库 > 【模板】倍增LCA [2017年5月计划 清北学堂51精英班 Day3]
【模板】倍增LCA [2017年5月计划 清北学堂51精英班 Day3]
P3379 【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：第一行包含三个正整数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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define max(a,b) ((a) > (b) ? (a) : (b)) 7 #define min(a,b) ((a) > (b) ? (b) : (a)) 8 #define lowbit(a) (a & (-(a))) 9 const int INF = 0x3f3f3f3f;10 const int MAXN = 500000 + 10;11 const int MAXM = 500000 + 10; 12 const int MAXX = 23;13 inline void read(int &x)14 {15 x = 0;char ch = getchar();char c = ch;16 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();17 while(ch >= ‘0‘ && ch <= ‘9‘)x = x * 10 + ch - ‘0‘,ch = getchar();18 if(c == ‘-‘)x = -x;19 }20 inline void swap(int &a,int &b)21 {22 int tmp = a;23 a = b;24 b = tmp;25 }26 int n, m, root, head[MAXN], cnt, tmp1, tmp2, deep[MAXN], lca[MAXN][MAXX];27 bool b[MAXN];28 29 struct Edge{int u,v,next;}edge[MAXN];30 void insert(int a,int b){edge[++cnt] = Edge{a, b, head[a]};head[a] = cnt;}31 32 void dfs(int v, int step)33 {34 b[v] = true;35 deep[v] = step;36 for(int pos = head[v];pos;pos = edge[pos].next)37 {38 int x = edge[pos].v; 39 if(!b[x])40 {41 lca[x][0] = v;42 dfs(x, step + 1);43 }44 }45 }46 void yu()47 {48 for(int j = 1;(1 << j) <= n;j ++)49 {50 for(int i = 1;i <= n;i ++)51 {52 if(lca[i][j - 1] != -1)53 {54 lca[i][j] = lca[lca[i][j - 1]][j - 1];55 }56 }57 }58 }59 int LCA(int va,int vb)60 {61 if(deep[va] < deep[vb])swap(va, vb);62 int i = 0,j = 0;63 for(;(1 << i) <= deep[va];i ++);64 i --;65 for(int j = i;j >= 0;j --)66 {67 if(deep[va] - (1 << j) >= deep[vb])68 va = lca[va][j];69 }70 if(va == vb)return va;71 for(j = i;j >= 0;j --)72 {73 if(lca[va][j] != -1 && lca[va][j] != lca[vb][j])74 {75 va = lca[va][j];76 vb = lca[vb][j];77 }78 }79 return lca[va][0];80 }81 int main()82 {83 read(n);read(m);read(root);84 for(int i = 1;i < n;i ++)85 {86 read(tmp1);read(tmp2);87 insert(tmp1, tmp2);88 insert(tmp2, tmp1);89 } 90 dfs(root, 0);91 yu();92 for(int i = 1;i <= m;i ++)93 {94 read(tmp1);read(tmp2);95 printf("%d\n", LCA(tmp1, tmp2));96 }97 return 0;98 }
【模板】倍增LCA [2017年5月计划 清北学堂51精英班 Day3]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。