倍增法

倍增思路相当于层序遍历，逐层或几层跳跃查，查询时间复杂度为 O(logn) ，空间复杂度为 O(nlogn)
对于每个结点先存储向上1层、2层、4层的结点，每个点有depth信息。

倍增法：构建一个 fa[i][j] 数组， i 结点向上 2^j 层的结点是谁，然后再统一下层数。先让他们同层数，然后二分搜索。后面是 log(树的长度)
j 的最大值还可以优化，对于每一个深度的结点就搞一个数组存最大 j 值 log2(j)

1
if(fa[u][j] == fa[v][j]) 不跳；//只跳到LCA的往下一对儿子

注意跳到根结点以上的越界情况的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Lutece  2144 吞吐量
//https://acm.uestc.edu.cn/contest/12/problem/B

//B题良心样例，5组数据错了4个，修了以后就AC了
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 100005, maxlog = 17, maxans = (int)1e9+1;
struct edgeS {
       int point;
       int distance;
};
list<edgeS> neigh[maxn];
edgeS up[maxn][maxlog] = { 0 };
int depth[maxn];
int dfs(int cur, int father)
{
       int i = 1;
       while ((1<<i) < depth[cur])
       {
               up[cur][i] = {
                      up[up[cur][i-1].point][i-1].point,
                      min(up[cur][i-1].distance, up[up[cur][i - 1].point][i -  1].distance)
               };
               i++;
       }
       list<edgeS>::iterator iter;
       for (iter = neigh[cur].begin(); iter != neigh[cur].end(); iter++)
       {
               if (iter->point != father)
               {
                      depth[iter->point] = depth[cur] + 1;
                      up[iter->point][0] = { cur, iter->distance };
                      dfs(iter->point, cur);
               }
       }
       return 0;
}
int main()
{
       ios::sync_with_stdio(0);
       cin.tie(0);
       int n, q;
       cin >> n >> q;
       for (int i = 1; i < n ; i++)
       {
               int a, b, d;
               cin >> a >> b >> d;
               neigh[a].push_back({ b, d });
               neigh[b].push_back({ a, d });
       }
       depth[1] = 1;
       for (int i = 1; i <= n; i++)
               for (int j = 0; j < maxlog; j++)
                      up[i][j].distance = maxans;
       dfs(1,0);
       for (int i = 0; i < q; i++)
       {
               int a, b, ans = maxans;
               cin >> a >> b;
               if (depth[a] > depth[b]) swap(a, b); // make sure b is deeper than a
               int diff = depth[b] - depth[a];
               int  j = 0;
               while (diff != 0)
               {
                      if (diff & (1<<j))
                      {
                              ans = min(ans, up[b][j].distance);
                              b = up[b][j].point;
                              diff ^= (1 << j);
                      }
                      j++;
               }
               if (a == b)
               {
                      cout << ans << endl;
                      continue;
               }
               for (int i = maxlog-1; i >= 0; i--)
               {
                      if (up[a][i].point != up[b][i].point) // excluding overflow that  are both 0
                      {
                              ans = min(min(ans, up[a][i].distance), up[b][i].distance);
                              a = up[a][i].point;
                              b = up[b][i].point;
                      }
               }
               ans = min(min(ans, up[a][0].distance), up[b][0].distance);
               cout << ans << "\n";
       }
}

Tarjan 离线算法

转载自：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.03.md

RMQ 在线算法

LCA to RMQ
LCA to RMQ

tql