斜二进制 LCA

· · 题解

本文介绍了一种基于斜二进制的 LCA 算法，算是一个省流，完整版请看 https://www.luogu.com.cn/article/u81tks5o。

写在前面：优劣一览。

本文介绍的算法此前在 Codeforces 有所出现，但是并未被引入 OI。笔者独立发明该算法（及其相关体系）后认为其值得被引入。其在 LCA 问题上有较大优势。

该算法复杂度为 O(n) 预处理 O(\log n) 查询。其对比树剖存在跑得更快，空间更少，代码更短，思路更简单的优势。

太长不看版：

void dfs(int x) {
  int p = fa[x], q = lb[p], r = lb[q];
  d[x] = d[p] + 1;
  lb[x] = d[p] - d[q] != d[q] - d[r] ? p : r;
  for (int y : es[x])
    if (y != p) fa[y] = x, dfs(y);
}
int lca(int u, int v) {
  if (d[u] < d[v]) swap(u, v);
  while (d[u] > d[v])
    if (d[lb[u]] < d[v])
      u = fa[u];
    else
      u = lb[u];
  while (u != v)
    if (lb[u] == lb[v])
      u = fa[u], v = fa[v];
    else
      u = lb[u], v = lb[v];
  return u;
}

如果不想了解原理的话可以直接背板，它并不长。

斜二进制是一种奇怪的进制。它从低到高第 i\ge1 位位权为 2^i-1。用斜二进制表示一个数时，需要满足至多一位为二且低于此位者均为零，其余位不超过一。定义一个斜二进制数的最低有效位是它最低位值非零的位。

我们将使用一种归纳构造的方式来生成每个自然数的斜二进制分解。0 的斜二进制是 0。我们假设已经对于 n 生成了它的斜二进制分解，那么 n+1 的斜二进制将在此基础上进行分类：

不妨这是第 i 位，那么乘上二的位值即为 2\times(2^i-1)=2^{i+1}-2，再加上新多出来的一就是 2^{i+1}-1。于是我们清除这两位并向前一位进一即可。

在第一位上加一即可。

不难验证以此法生成的斜二进制分解符合它应有的性质。

这么讲可能比较抽象，我们来举点例子。

总之大概就是这样。注意我们并不关心一个数的斜二进制是否唯一。

我们定义 \textit{skew\_lowbit}(x) 表示 x 在斜二进制下的最低有效位的位权。我们定义 d_x 为树上一个点到根路径上的节点数，称为该节点的“深度”。我们定义 \textit{lb}_x 为一个点 x 的 \textit{skew\_lowbit}(d_x) 级祖先。若该祖先不存在，则定义其为 0。定义 d_0=\textit{lb}_0=\textit{skew\_lowbit}(0)=0。可以发现，d_x-d_{\textit{lb}_x}=\textit{skew\_lowbit}(d_x)。也即，d_{\textit{lb}_x} 是 d_x 在斜二进制下将最低有效位减一后的结果。

我们考虑怎么递推这个 lb。我们考虑现在要计算 lb_x。我们定义 p 为 x 的父亲 \textit{fa}_x，q 为 \textit{lb}(p)，r 为 \textit{lb}(q)。我们考虑将 d_p 加上 1 转移到 d_x 只有两种可能性：若 d_p 在斜二进制下的最低有效位上不为 2，则将其最低位直接修改为 1；此时，\textit{skew\_lowbit}(d_x)=1，也即 \textit{lb}_x=p。若 d_p 在斜二进制下的最低有效位上为 2，则对其进行进位；此时，\textit{skew\_lowbit}(d_p)=\textit{skew\_lowbit}(d_q)，且 \textit{lb}_x=r。手玩一下斜二进制，这是简单的。

现在我们考虑怎么用求出的 \textit{lb} 求 LCA。我们直接看开头的这段代码：

int lca(int u, int v) {
  if (d[u] < d[v]) swap(u, v);
  while (d[u] > d[v])
    if (d[lb[u]] < d[v])
      u = fa[u];
    else
      u = lb[u];
  while (u != v)
    if (lb[u] == lb[v])
      u = fa[u], v = fa[v];
    else
      u = lb[u], v = lb[v];
  return u;
}

它的正确性是显而易见的，因为对于 d_x=d_y 一定有 d_{\textit{lb}_x}=d_{\textit{lb}_y}。于是我们只需要证明它的复杂度。上下两个 while 的本质是相同的，即为从 u 开始找到一个最低的满足某个条件的祖先。

我们以上面那个 while 为例：

  while (d[u] > d[v])
    if (d[lb[u]] < d[v])
      u = fa[u];
    else
      u = lb[u];

在第一次走第一个 if 之前，u 会一直跳到 \textit{lb}_u。由于 d_u 的斜二进制最低有效位上至多为 2，这里我们每至多两步就会让 d_u 斜二进制的最低有效位升高。由于这个有效位至多升高到 O(\log n)，这一部分的复杂度也是 O(\log n)。

在第一次走第一个 if 之后，设每次走一次第一个 if 之前 \textit{skew\_lowbit}(d_u)=w，则下一个 \textit{skew\_lowbit}(d_{u'})\ge w 的点 u' 正是 lb_u，而它已经被我们宣告不合法了。于是每走一次 if 都会带来 d_u 斜二进制的最低有效位降低，且无法再次升高。进一步，根据斜二进制的退位特征，我们发现走一次 if 一定会使该有效位降低恰一位。而每至多两步第二个 if 就会让 d_u 斜二进制的最低有效位升高，于是每次第一个 if 后至多跟着一次第二个 if。而第一个 if 的总数量是 O(\log n) 的，于是总复杂度也是 O(\log n) 的。

于是我们得到了一个 O(n) 预处理 O(\log n) 查询的简单 LCA 算法，做完了。