在一棵有根树里，两个节点的最近公共祖先即两个点的公共祖先里深度最大的，记点集 \(S=(v_1,v_2,\cdots,v_n)\) 的最近公共祖先 \(LCA(v_1,v_2,\cdots,v_n)\) 或 \(LCA(S)\)。

  朴素算法是：dfs 求出每个点深度，假设 y 深度比 x 大，让 y 向上走至与 x 同等深度，之后 x 与 y 一起向上走直到相遇，时间复杂度 \(O(n)\)。

模板 hdu2586

RMQ 问题

  RMQ(Range Minimum/Maximum Query) 问题是指在长度为 n 的序列 \(a\) 里，求区间 \([l,r]\) 中的最大值。

  ST 表用于解决可重复贡献问题。ST 表基于倍增思想，\(O(n\log{n})\) 处理，\(O(1)\) 回答每个询问，不支持修改。

  记 \(f(i,j)\) 表示区间 \([i,i+2^j-1]\) 的最大值。则 \(f(i,0)=a_i\)，转移方程 \(f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))\)。对于每个询问 \([l,r]\)，令 \(k=\log_2(r-l+1)\)，则答案为 \(f(l,k)\) 与 \(f(r-2^k+1,k)\) 二者中的最大值。

模板题

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int n, m;
int a[N], f[N][20], mn[N];

void init() {
  mn[0] = -1;
  for (int i = 1; i <= n; ++i) {
    mn[i] = (i&(i-1)) == 0 ? mn[i-1] + 1 : mn[i-1];
    f[i][0] = a[i];
  }
  for (int j = 1; j <= mn[n]; ++j)
    for (int i = 1; i + (1<<j) - 1 <= n; ++i)
      f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}

int query(int l, int r) {
  int k = mn[r-l+1];
  return max(f[l][k], f[r-(1<<k)+1][k]);
}

int main() 
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  init();
  int x, y;
  while (m--) {
    scanf("%d%d", &x, &y);
    printf("%d\n", query(x, y));
  }
    return 0;
}

树上倍增法

  记 \(f(i,k)\) 表示 \(i\) 的 \(2^k\) 辈祖先，则 \(f[i,0]\) 即为 \(i\) 的父节点，且有 \(f[i,k]=f[f[i,k-1],k-1]\)，可以对树进行 bfs 预处理，时间复杂度 \(O(n\log{n})\)，每次查询时间复杂度 \(O(\log{n})\)，从而考虑一下算法：

  假设 \(d[x]\le d[y]\)，将 \(y\) 向上走至与 \(x\) 同一高度处，若 \(x==y\)，则已找到，否则把 \(x,y\) 同时向上调整保证深度一致且二者不相遇，最后 \(x,y\) 只差一步相遇，父节点即为 \(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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 4e4 + 5;

int t, n, m, tot, k;
int f[N][20], d[N], dis[N], head[N], lg[N];
int ver[N<<1], edge[N<<1], nxt[N<<1];

void add(int x, int y, int z) {
  ver[++tot] = y; edge[tot] = z; nxt[tot] = head[x]; head[x] = tot;
}

void bfs() {
  queue<int> q;
  q.push(1);
  d[1] = 1;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = ver[i];
      if (d[y]) continue;
      d[y] = d[x] + 1;
      dis[y] = dis[x] + edge[i];
      f[y][0] = x;
      for (int j = 1; j <= k; ++j)
        f[y][j] = f[f[y][j-1]][j-1];
      q.push(y);
    }
  }
}

int lca(int x, int y) {
  if (d[x] > d[y]) swap(x, y);
  for (int i = k; i >= 0; --i)
    if (d[f[y][i]] >= d[x]) y = f[y][i];
  if (x == y) return x;
  for (int i = k; i >= 0; --i)
    if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
  return f[x][0];
}

int main() 
{
  scanf("%d", &t);
  for (int i = 2; i < N; ++i) lg[i] = lg[i/2] + 1;
  while (t--) {
    scanf("%d%d", &n, &m);
    k = lg[n] + 1;
    for (int i = 1; i <= n; ++i) head[i] = d[i] = 0;
    tot = 0; 
    int x, y, z;
    for (int i = 1; i < n; ++i) {
      scanf("%d%d%d", &x, &y, &z);
      add(x, y, z);
      add(y, x, z);
    }
    bfs();
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &x, &y);
      printf("%d\n", dis[x] + dis[y] - 2 * dis[lca(x, y)]);
    }
  }
    return 0;
}

LCA 的 Tarjan 算法

  使用并查集对向上标记法的优化，是离线算法。具体的思想是在 dfs 时对树的节点进行分类：

  1. 已访问但未回溯的节点添加标记 1，这些节点是当前访问节点 \(x\) 及 \(x\) 的祖先。
  2. 已访问并且回溯的节点添加标记 2。
  3. 未访问的节点标记 0。

  对于正在访问的节点 x，它到根节点的路径已标记为 1。若 y 是已经访问且回溯的节点，则 \(LCA(x,y)\) 就是 \(y\) 向上走到根，第一个遇到的标记为 1 的节点。可以用并查集优化，当节点标记为 2 时，把它所在集合合并到父节点所在集合。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 4e4 + 5, M = 205;

int t, n, m, tot;
int fa[N], d[N], v[N], ans[M];
int ver[N<<1], edge[N<<1], nxt[N<<1], head[N];

vector<int> q[N], qid[N]; 

void add(int x, int y, int z) {
  ver[++tot] = y; edge[tot] = z; nxt[tot] = head[x]; head[x] = tot;
}

void addquery(int x, int y, int id) {
  q[x].push_back(y), qid[x].push_back(id);
  q[y].push_back(x), qid[y].push_back(id);	
}

int find(int x) {
  if (x == fa[x]) return x;
  return fa[x] = find(fa[x]);
}

void tarjan(int x) {
  v[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (v[y]) continue;
    d[y] = d[x] + edge[i];
    tarjan(y);
    fa[y] = x;
  }
  for (int i = 0; i < (int)q[x].size(); ++i) {
    int y = q[x][i], id = qid[x][i];
    if (v[y] == 2) {
      int lca = find(y);
      ans[id] = min(ans[id], d[x] + d[y] - 2 * d[lca]);
    }
  }
  v[x] = 2;
}

int main() 
{
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
      head[i] = 0; fa[i] = i; v[i] = 0;
      q[i].clear(); qid[i].clear();
    }
    tot = 0;
    int x, y, z;
    for (int i = 1; i < n; ++i) {
      scanf("%d%d%d", &x, &y, &z);
      add(x, y, z);
      add(y, x, z);
    }
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &x, &y);
      if (x == y) { ans[i] = 0; continue; }
      addquery(x, y, i);
      ans[i] = INF;
    }
    tarjan(1);
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  }
    return 0;
}