LCA (最近公共祖先) Tarjan & 倍增Harington的博客-

LCA Tarjan：

实现原理

理解：离线算法，建好树后再查询，一次DFS 吧所有查询解决完。

时间复杂度：O(n+q)；

n个点 q次询问

补一下：链式向前星，并查集 ，Tarjan

代码

 #include<iostream> #include<math.h> #include<stdio.h> #include<algorithm> #include<cstring> using namespace std; const int MAXN = 5e5+ 10; int fa[MAXN], head[MAXN], head_ask[MAXN], cnt, cnt_ask, ans[MAXN]; bool vis[MAXN]; int n, m, s; struct Edge{  int to, dis, next;  int num; }edge[MAXN << 1], ask[MAXN << 1];  void add_edge(int u, int v, int dis) {  edge[++cnt].to = v;  edge[cnt].next = head[u];  head[u] = cnt; } void add_ask(int x, int y, int num) { //num 第几个查询  ask[++cnt_ask].to = y;  ask[cnt_ask].num = num; //第几个查询   ask[cnt_ask].next = head_ask[x];  head_ask[x] = cnt_ask; } int find(int x) { //并查集   return fa[x] == x ? x : fa[x] = find(fa[x]); } void init() {  cnt = 1;  cnt_ask = 1;  memset(vis, 0, sizeof(vis));  fa[n] = n; } void Tarjan(int x) {  vis[x] = true;  for(int i = head[x]; i ; i = edge[i].next) {   int to = edge[i].to;   if( !vis[to] ) {    Tarjan(to);    fa[to] = x;   }  }  for(int i = head_ask[x]; i; i = ask[i].next) {   int to = ask[i].to;   if( vis[to] ){     ans[ask[i].num] = find(to);   }  } } int main () {  ios::sync_with_stdio(0);     cin.tie(0);  cin >> n >> m >> s;  int x, y;  init();  for(int i = 1; i < n; ++i) {   fa[i] = i;   cin >> x >> y;   add_edge(x, y, 0);   add_edge(y, x, 0);  }  for(int i = 1; i <= m; ++i) {   cin >> x >> y;   add_ask(x, y, i);   add_ask(y, x, i);  }   Tarjan(s);    for(int i = 1; i <= m; ++i) {   cout << ans[i] << endl;  } } 

练习题：

洛谷 P3379

LCA 倍增：

倍增原理

理解：

1) 在线算法

2）暴力的优化，不是一步一步向上找节点，每次走 步

模板待补