lca最近公共祖先（模板）

洛谷上的lca模板题——传送门

1.tarjan求lca

学了求lca的tarjan算法（离线），在洛谷上做模板题，结果后三个点超时。

又把询问改成链式前向星，才ok。

这个博客，tarjan分析的很详细。

附代码——

#include <cstdio> #include <cstring> const int maxn = 500001; int n, m, cnt, s, cns; int x, y, z[maxn];//z是x和y的lca int f[maxn], head[maxn], fr[maxn]; bool vis[maxn]; struct node e[2 * maxn]; struct Node q[2 * maxn]; inline int read()//读入优化 while(ch >= '0' && ch <= '9') return x * f; } inline void ask(int u, int v, int i)//储存待询问的结构体，也是链式前向星优化 inline void add(int u, int v)// inline int find(int a) /*inline void Union(int a, int b) */ inline void tarjan(int k) for(i = fr[k]; i != 1; i = q[i].next) if(vis[q[i].to] == 1) z[q[i].num] = find(q[i].to); } int main() for(i = 1; i <= m; i++) tarjan(s); for(i = 1; i <= m; i++) printf("%d\n", z[i]); return 0; }
View Code

进过培训，修改了代码

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 500001 11 using namespace std; 12 13 inline int get_num() 20 21 int n, m, s; 22 int fa[MAXN], qx[MAXN], qy[MAXN], ans[MAXN], f[MAXN]; 23 vector <int> vec[MAXN], q[MAXN]; 24 25 inline int find(int x) 26 29 30 inline void dfs(int u) 31 39 for(i = 0; i < q[u].size(); i++) 40 if(f[v = u ^ qx[q[u][i]] ^ qy[q[u][i]]]) 41 ans[q[u][i]] = find(v); 42 fa[u] = f[u]; 43 } 44 45 int main() 46 58 for(i = 1; i <= m; i++) 59 65 dfs(s); 66 for(i = 1; i <= m; i++) printf("%d\n", ans[i]); 67 return 0; 68 }
View Code

其实上面两个代码有些重复运算，请手动把求lca的过程放到dfs上面（也就是遍历到这个节点就求lca，而不是遍历完再求）

2.倍增求lca

下面是求lca的倍增算法（在线）。

1.DFS预处理出所有节点的深度和父节点

inline void dfs(int u) } }
dfs预处理

2.初始各个点的2^j祖先是谁 ,其中2^j(j=0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。

void init()
初始化

3.从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。

否则，利用倍增法找到最小深度的p[a][j]!=p[b][j]，此时他们的父亲p[a][0]即lca。

int lca(int a,int b)//最近公共祖先 } return p[a][0]; }
倍增求lca

最后是完整代码，为了节约时间，就没有把p数组初始化为1.

#include <cstdio> #include <cstring> #include <iostream> const int maxn = 500001; int n, m, cnt, s; int next[2 * maxn], to[2 * maxn], head[2 * maxn], deep[maxn], p[maxn][21]; inline void add(int x, int y) inline void dfs(int i) } inline void init() inline int lca(int a, int b) return p[a][0]; } int main() deep[s] = 1; dfs(s); init(); for(i = 1; i <= m; i++) return 0; }
View Code

经过培训，又改了改代码。

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 500001 11 using namespace std; 12 13 inline int get_num() 20 21 int n, m, s; 22 int f[MAXN][25], deep[MAXN]; 23 vector <int> vec[MAXN]; 24 25 inline void dfs(int u) 26 35 } 36 37 inline int lca(int x, int y) 38 50 51 int main() 52 64 dfs(s); 65 for(i = 1; i <= m; i++) 66 70 return 0; 71 }
View Code

3.树剖法求lca

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 500001 11 using namespace std; 12 13 inline int get_num() 20 21 int n, m, s; 22 int f[MAXN], size[MAXN], top[MAXN], son[MAXN], deep[MAXN]; 23 vector <int> vec[MAXN]; 24 25 inline void dfs1(int u) 26 40 } 41 } 42 43 inline void dfs2(int u, int tp) 44 54 } 55 56 inline int lca(int x, int y) 57 if(deep[x] > deep[y]) swap(x, y); 64 return x; 65 } 66 67 int main() 68 80 dfs1(s); 81 dfs2(s, s); 82 for(i = 1; i <= m; i++) 83 88 return 0; 89 }
View Code

上一篇：Divide Groups（分组）（二分图染色）

下一篇： 遇到的Docker常用命令

---

lca 模板 tarjan 树链剖分 倍增