学习笔记 - LCA 求法总结

LCA：Lowest Common Ancestor，树上最近公共祖先。

树上倍增

树上倍增 - 思路

对于一个询问，我们可以考虑两个点深度相等的时候同时向上跳，不等就跳到相等，LCA 就是两者第一次跳到重合的点。这么做是 $O(n)$ 的。

发现太慢了，考虑一次可不可以多跳一点。考虑倍增。设 $jump_{i,j}$ 为点 $i$ 跳了 $2^j$ 步之后的点，即 $2^j$ 级祖先。对于一个询问，我们就由大倍往小倍一个一个试跳。如果跳到同一个点，那么可能就超过 LCA 了。所以跳到最高的不同的两个点，此时再跳一步必然重合，也就是说这两个点必为兄弟，父亲即为 LCA。这么做，在跳两个点深度相等时也可以二进制分解，倍增地跳。如果一者是另一者祖先，那么这一步就可以判定出来然后返回了。

具体实现来说，我们把 $jump$ 数组和每个点的深度在一次 dfs 中预处理。 $jump_{i,0}$ 必为其父亲，别的可以用 $2^i=2^{i-1}+2^{i-1}$ 来合并，也就是可以 $jump_{i,j}=jump_{jump_{i,j-1},j-1}$ 。在每一次询问中，先看两个点的深度差，二进制分解，跳到深度相等为止。如果此时两点重合，显然是因为一点是另一点祖先，返回该点即可。然后从大倍往小倍试，跳到最高而不重合，返回这对兄弟的父亲即可。

空间 $O(n\log n)$ ，时间 $O(n\log n)-O(\log n)$ 。

优点：思路简单。

缺点：复杂度较大。

树上倍增 - 代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 500005;
constexpr int MXLG = 19;
int N, M, S;
int head[MXN], to[MXN << 1], nxt[MXN << 1], egsz;
int depth[MXN], jump[MXN][MXLG];

inline void addedge(int x, int y) {
  to[egsz] = y, nxt[egsz] = head[x], head[x] = egsz++;
  to[egsz] = x, nxt[egsz] = head[y], head[y] = egsz++;
}
void pre(int f, int x, int d) {
  depth[x] = d;
  fill(jump[x], jump[x] + MXLG, -1);
  jump[x][0] = f;
  for (int i(1); (1 << i) <= d; ++i) jump[x][i] = jump[jump[x][i - 1]][i - 1];
  for (int i(head[x]); ~i; i = nxt[i]) {
    if (to[i] == f) continue;
    pre(x, to[i], d + 1);
  }
}
int query(int x, int y) {
  if (depth[x] < depth[y]) swap(x, y);
  int diff(depth[x] - depth[y]);
  for (int i(MXLG - 1); ~i; --i)
    if (diff & (1 << i)) x = jump[x][i];
  if (x == y) return x;
  for (int i(MXLG - 1); ~i; --i)
    if (jump[x][i] ^ jump[y][i]) x = jump[x][i], y = jump[y][i];
  return jump[x][0];
}
int main() {
  scanf("%d%d%d", &N, &M, &S);
  --S;
  fill(head, head + N, -1);
  for (int i(1), x(0), y(0); i != N; ++i) {
    scanf("%d%d", &x, &y), --x, --y;
    addedge(x, y);
  }
  pre(-1, S, 0);
  for (int x(0), y(0); M--;) {
    scanf("%d%d", &x, &y), --x, --y;
    int ans(query(x, y));
    ++ans, printf("%d\n", ans);
  }
  return 0;
}

Tarjan 离线算法

Tarjan 离线算法 - 思路

考虑对于一个点，它子孙与它的 LCA 是它自己，它兄弟及兄弟的子孙与它的 LCA 是他的父亲，它爷爷的其他孩子及子孙与它的 LCA 是它的爷爷……

思考这样一个过程——我在一个点全部遍历完之后，把它与父亲的连边启用，意思类似于合并它与它的父亲。

考虑点 $p$ 已被访问，在访问点 $q$ 的时候要回答 $\operatorname{LCA}(p,q)$ 的询问。此时与点 $p$ 合并在一起的最高的点 $a$ 一定是 $p$ 的祖先，并且这个 $a$ 还没有遍历完，否则 $a$ 也会被和它的父亲合并。既然如此， $q$ 就必然是这个 $a$ 的子孙。那么，点 $a$ 就是 LCA，因为它是公共祖先，同时不会存在更低的公共祖先，因为更低的公共祖先子孙已经遍历完，不可能是 $q$ 的祖先。

如果我要在一次 dfs 里面解决所有询问，那么一个询问一定有一种写法，使得当我访问到其中一个节点的时候，另一个已经被访问过了。所以对于这种形式的询问，只要动态维护另一个点的答案即可。

例如样例的 $\operatorname{LCA}(2,3)$ 。假设先遍历 $2$ ，然后就可以将 $2$ 与 $4$ 合并，因为只要不是它的子孙，就不可能与它的 LCA 是它自己，所以答案都可以是 $4$ 。当我遍历到 $3$ 的时候，就更新其答案为 $4$ 。

这个合并实际上就是并查集。

具体一些，就是我把每个询问正反各加入一次，这一步可以用链表/vector 维护。在一次 dfs 中，先往下 dfs，否则对于一个为另一个祖先的询问永远不会被回答到。每遍历完一个儿子，就让它与自己合并，以自己为根。然后一个一个处理询问，对于另一个点还未遍历过的询问就跳过，否则答案就是另一个点所在并查集的根。

时间复杂度：使用路径压缩并查集，就是 $O((n+m)\alpha(n))$ （ $\alpha$ 是反阿克曼函数~~众所周知就是常数~~）。

空间复杂度： $O(n+m)$ 。

优点：效率极高。

缺点：思路有点绕弯。

Tarjan 离线算法 - 代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 500005;
int N, M, S;
int head[MXN], to[MXN << 1], nxt[MXN << 1], egsz;
int ahead[MXN], ato[MXN << 1], anxt[MXN << 1], asz;
int fa[MXN];
bool vis[MXN];
int ans[MXN];

inline void addedge(int x, int y) {
  to[egsz] = y, nxt[egsz] = head[x], head[x] = egsz++;
  to[egsz] = x, nxt[egsz] = head[y], head[y] = egsz++;
}
inline void addask(int x, int y) {
  ato[asz] = y, anxt[asz] = ahead[x], ahead[x] = asz++;
  ato[asz] = x, anxt[asz] = ahead[y], ahead[y] = asz++;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void dfs(int f, int x) {
  vis[x] = true;
  for (int i(head[x]); ~i; i = nxt[i]) {
    if (to[i] == f) continue;
    dfs(x, to[i]);
    fa[find(to[i])] = x;
  }
  for (int i(ahead[x]); ~i; i = anxt[i]) {
    if (!vis[ato[i]]) continue;
    ans[i >> 1] = find(ato[i]);
  }
}
int main() {
  scanf("%d%d%d", &N, &M, &S);
  --S;
  fill(head, head + N, -1);
  fill(ahead, ahead + N, -1);
  for (int i(0); i != N; ++i) fa[i] = i;
  for (int i(1), x(0), y(0); i != N; ++i) {
    scanf("%d%d", &x, &y), --x, --y;
    addedge(x, y);
  }
  for (int i(0), x(0), y(0); i != M; ++i) {
    scanf("%d%d", &x, &y), --x, --y;
    addask(x, y);
  }
  dfs(-1, S);
  for (int i(0); i != M; ++i) {
    ++ans[i], printf("%d\n", ans[i]);
  }
  return 0;
}

欧拉序 RMQ

欧拉序 RMQ - 思路

首先我们要知道欧拉序是什么。

每经过一次点（包括从父亲到自己或者儿子遍历完回到自己）就在欧拉序中记录一次。例如样例的一个欧拉序就是 4 2 4 1 3 1 5 1 4。

那么对于两个点，它们的非最低公共祖先不可能存在于他们在欧拉序中两个位置之间，根据定义即可理解。反之，它们的非公共祖先可能不出现，也可能出现，但是一定不会高过最低公共祖先。最低公共祖先也一定会出现，这个根据定义即可理解啊……

例如这里的 $\operatorname{LCA}(2,3)$ ，因为最低公共祖先要换一个儿子来遍历，所以这里之间 $4$ 会出现一次。反之， $3$ 和 $5$ 之间就没有 $4$ ，但是有 $1$ ，是最高点。

所以对于每个询问，只要知道它在欧拉序上两个端点之间（包括）最高的点就可以了，这里一个点虽然可能出现多次，任意一个即可，这个比较好想的。

那不就是 RMQ 吗。

这个 RMQ 理论上来说用 Sparse Table 或线段树都可以，但是一般都用 Sparse Table，此时询问 $O(1)$ 。

空间 $O(n\log n)$ ，时间 $O(n\log n)-O(1)$ 。

优点：思路清奇，快。

缺点：写的多一点。

欧拉序 RMQ - 代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 500005;
constexpr int MXLG = 20;
int N, M, S;
int head[MXN], to[MXN << 1], nxt[MXN << 1], egsz;
int depth[MXN], pos[MXN];
int lg[MXN << 1], seq[MXLG][MXN << 1], sl;

inline int cmp(int x, int y) {
  return depth[x] < depth[y] ? x : y;
}
inline void addedge(int x, int y) {
  to[egsz] = y, nxt[egsz] = head[x], head[x] = egsz++;
  to[egsz] = x, nxt[egsz] = head[y], head[y] = egsz++;
}
void dfs(int f, int x, int d) {
  depth[x] = d;
  pos[x] = sl;
  seq[0][sl++] = x;
  for (int i(head[x]); ~i; i = nxt[i]) {
    if (to[i] == f) continue;
    dfs(x, to[i], d + 1);
    seq[0][sl++] = x;
  }
}
int query(int l, int r) {
  int n(lg[r - l]);
  return cmp(seq[n][l], seq[n][r - (1 << n)]);
}

int main() {
  scanf("%d%d%d", &N, &M, &S);
  --S;
  fill(head, head + N, -1);
  for (int i(1), x(0), y(0); i != N; ++i) {
    scanf("%d%d", &x, &y), --x, --y;
    addedge(x, y);
  }
  dfs(-1, S, 0);
  lg[0] = -1, lg[1] = 0;
  for (int i(2); i <= sl; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i(1); (1 << i) <= sl; ++i) {
    for (int j(0); j + (1 << (i - 1)) <= sl; ++j) {
      seq[i][j] = cmp(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int x(0), y(0); M--;) {
    scanf("%d%d", &x, &y), --x, --y;
    int ans(query(min(pos[x], pos[y]), max(pos[x], pos[y]) + 1));
    ++ans, printf("%d\n", ans);
  }
  return 0;
}

dfs 序 RMQ

dfs 序 RMQ - 思路

从 ckj 的 blog 里面学来的另一种 $O(1) \operatorname{LCA}$ 写法。stO ckj Orz。

考虑 dfs 序有什么性质：一个子树是连续的，根在第一位，后面是一棵棵连续的子树。也就是说，一个点的祖先一定在它的前面。

假设询问的两个点的 dfs 序上位置是 $p,q$ ，答案的 dfs 序上位置是 $a$ 。

分类讨论：

$p\neq a$ 。

在 dfs 序中， $a$ 就是最靠前的，路径应该是 $a$ 下到 $p$ ，然后回来，进入另一个 $a$ 的儿子，下去到 $q$ 。意思是说， $[p,q]$ 一定有一个 $a$ 的儿子，而且也必然没有深度更浅的点了。

所以可以 RMQ 求 $[p,q]$ 之间最浅的点，取父亲即可。

$p=a$ 。

我们当然可以特判。但这样多一个数组。

考虑 $[p,q]$ 也一定有一个 $p$ 的儿子，那也就是说， $[p+1,q]$ 里面最浅的点是 $p$ 的儿子。代回到上一个情况，发现也是合法的，不会漏判。

所以——我们还是要特判的，判 $p=q$ 时。

空间 $O(n\log n)$ ，时间 $O(n\log n)-O(1)$ 。

优点：保持时间优势的同时时空常数更小。

缺点：有点难找。可能没有前者好理解、以及容易漏特判？

dfs 序 RMQ - 代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 500005;
constexpr int MXLG = 19;
int N, M, S;
int head[MXN], to[MXN << 1], nxt[MXN << 1], egsz;
int depth[MXN], pos[MXN], fa[MXN];
int lg[MXN], seq[MXLG][MXN], sl;

inline int cmp(int x, int y) { return depth[x] < depth[y] ? x : y; }
inline void addedge(int x, int y) {
  to[egsz] = y, nxt[egsz] = head[x], head[x] = egsz++;
  to[egsz] = x, nxt[egsz] = head[y], head[y] = egsz++;
}
void dfs(int f, int x, int d) {
  depth[x] = d;
  pos[x] = sl;
  fa[x] = f;
  seq[0][sl++] = x;
  for (int i(head[x]); ~i; i = nxt[i]) {
    if (to[i] == f) continue;
    dfs(x, to[i], d + 1);
  }
}
int query(int l, int r) {
  int n(lg[r - l]);
  return cmp(seq[n][l], seq[n][r - (1 << n)]);
}

int main() {
  scanf("%d%d%d", &N, &M, &S);
  --S;
  fill(head, head + N, -1);
  for (int i(1), x(0), y(0); i != N; ++i) {
    scanf("%d%d", &x, &y), --x, --y;
    addedge(x, y);
  }
  dfs(-1, S, 0);
  lg[0] = -1, lg[1] = 0;
  for (int i(2); i <= N; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i(1); (1 << i) <= N; ++i) {
    for (int j(0); j + (1 << (i - 1)) <= N; ++j) {
      seq[i][j] = cmp(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int x(0), y(0); M--;) {
    scanf("%d%d", &x, &y), --x, --y;
    int ans(x ^ y ? fa[query(min(pos[x], pos[y]) + 1, max(pos[x], pos[y]) + 1)]
                  : x);
    ++ans, printf("%d\n", ans);
  }
  return 0;
}

树链剖分

树链剖分 - 思路

同样的话没法再说一遍。最多就是并不需要 $dfn$ 和 $rdfn$ 数组。

空间复杂度： $O(n)$ 。

时间复杂度： $O(n)-O(\log n)$ 。

优点：树剖比较通用。

缺点：代码较长，数组多（虽然只有 LCA 的时候看起来并不多呀）。

斜二进制倍增

斜二进制倍增 - 思路

详见原作者出处。

简单来说就是摒弃掉二进制意义的倍增，而改为斜二进制，然后你发现空间复杂度丢掉了一只 $\log$ 。

空间复杂度： $O(n)$ 。

时间复杂度： $O(n)-O(\log n)$ 。

优点：在所有单次查询 $O(\log n)$ 的做法里面，常数和代码长度几乎是最优的。

缺点：在长剖求 k 级祖先问题中无法打败二进制倍增。

斜二进制倍增 - 代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 500005;
int N, M, S;
vector<int> to[MXN];
int dep[MXN], fa[MXN], lb[MXN];

void pre(int p, int f) {
  dep[p] = dep[f] + 1, fa[p] = f;
  int x(lb[f]), y(lb[x]);
  lb[p] = (dep[f] + dep[y] == dep[x] * 2 ? y : f);
  for (int q : to[p]) if (q ^ f) pre(q, p);
}
int getlca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  while (dep[x] > dep[y]) x = (dep[lb[x]] >= dep[y] ? lb : fa)[x];
  while (x ^ y) lb[x] ^ lb[y] ? (x = lb[x], y = lb[y]) : (x = fa[x], y = fa[y]);
  return x;
}

int main() {
  scanf("%d%d%d", &N, &M, &S);
  for (int i(1), x(0), y(0); i != N; ++i)
    scanf("%d%d", &x, &y), to[x].push_back(y), to[y].push_back(x);
  pre(S, 0);
  for (int x(0), y(0); M--;)
    scanf("%d%d", &x, &y), printf("%d\n", getlca(x, y));
  return 0;
}

学习笔记

#树

学习笔记 - LCA 求法总结

http://sunsetglow95.github.io/note-lca/

作者

SunsetGlow95

发布于

2022年11月10日

许可协议

题解 - P8884 「JEOI-R1」棋上一篇

游记 - CSP-J/S 2022 第二轮 VP 下一篇