线性时间 Level Ancestor 问题

很早之前写过两篇线性时间的 LCA & RMQ 的做法。现在把四毛子的另外一个例子补完。

The Problem

所谓 Level Ancestor 问题 $LA (x, k)$ ，是形如这样的询问：

$x$ 这个点的 $k$ 级祖先是谁？

我们的任务是，给定一颗有根树，回答若干次这样的询问。要求复杂度 $O (n + q)$ ，其中 $n$ 是树的节点数， $q$ 是查询数目，问题是在线的。下文中使用 $⟨ f (n), g (n) ⟩$ 表示解法复杂度为 $O (f (n) + q \times g (n))$ ，即预处理复杂度 $f (n)$ ，查询复杂度 $g (n)$ 。

在下文中，记一个节点的深度 $depth (x)$ 表示 $x$ 到根的节点数，记一个节点的高度 $height (x)$ 表示 $x$ 下方的子树的所有节点到 $x$ 的距离最大值（距离定义为路径上的点数），记一个节点的子树大小 $size (x)$ 为其子树的节点数。

The Solution

Trick 1, Path Decomposition

第一个技巧是链剖分。首先大家都熟知重链剖分，在重链剖分之后每个节点到根的路径上的轻边只有 $O (\log n)$ 条。

因此我们只要不断向上跳，直到寻找一个包含第 $1$ 级祖先的重链，然后在每条重链上用一个数组记录每个位置的节点标号即可。注意到每个节点只会在它所在的树链里面被记录一次，因此这样空间复杂度和预处理复杂度是 $O (n)$ 的。这样做的复杂度是 $⟨ O (n), O (\log n) ⟩$ 。如果使用长链剖分，我们会得到更劣的结果。

Trick 2, Binary Lifting

下一个熟知的技巧是倍增。对于每个节点 $x$ ，我们可以记录 $O (\log n)$ 个值， $t r (x, i)$ 表示 $x$ 的 $2^{i}$ 级祖先。借助 $t r (x, i) = t r (t r (x, i - 1), i - 1)$ ，我们可以简单地在 $O (n \log n)$ 的时间中计算出整个 $t r$ ，然后在求 $LA (x, k)$ 时，可以将 $k$ 拆成 $O (\log k)$ 个 $2^{i}$ 的和，分别跳即可。这一实现的复杂度是 $⟨ O (n \log n), O (\log n) ⟩$ 。

Trick 3, Ladders

我们将上述两个技巧结合起来。首先，我们假设要求 $LA (x, k)$ ，其中 $k$ 最高的二进制位是 $2^{j}$ 。设 $y \overset{def}{=} t r (x, j)$ 。注意到， $y$ 所在的长链的长度 $\geq height (y) \geq 2^{j} > k - 2^{j}$ 。对于每一条长链，（原本我们记录长链每一个位置的总共 $l$ 个元素， $l$ 为链长度，）我们额外记录链上方的 $l$ 个节点，把这 $l$ 个点叫长链的梯子（Ladder）。这样，我们就可以跳一次倍增、跳一次梯子，仅利用两次来求算 $ $ 。这一做法的复杂度是 $⟨ O (n \log n), O (1) ⟩$ 。

Trick 4, Mo4R

首先我们可以发现，我们的只需要记录所有叶子节点的 $t r$ 即可，因为一个 $LA (x, k)$ 询问一定可以变成一个 $LA (y, depth (x) - depth (y) + k)$ 的问题，其中 $y$ 是 $x$ 下方的任一叶子节点。假设叶子节点有 $n_{L}$ 个，那么我们预处理的复杂度就是 $O (n_{L} \times \log n)$ 。下文，我们利用一些手段去降低 $n_{L}$ 。为此我们采用四个俄罗斯人方法（Method of Four Russians，四毛子）。

设 $k = \frac{\log n}{4}$ 。我们称一个节点是宏节点，表示其子树大小 $> k$ ；否则称其为微节点。

所有宏节点会形成一颗树，称之为宏树。宏树的每个叶子在原树中大小 $\geq k$ ，因此宏树的叶子至多只有 $O (\frac{n}{k}) = O (\frac{n}{\log n})$ 个。在宏树上利用 Trick 3 的长链剖分搭梯子、叶子节点倍增的方法，可以 $⟨ O (n), O (1) ⟩$ 解决宏树上的询问。

考虑微节点形成的微连通块，每个这样的块都是原树的子树，且大小不超过 $k$ ；这就意味着微连通块只有不超过 $2^{2 k} = \sqrt{n}$ 种（考虑其括号序列）。对于其中每一种我们都可以暴力在 $O (k^{2}) = O (\log^{2} n)$ 的时间内求出块内的 $LA$ 。对于块外的询问，可以先跳到块根的父亲上，然后在宏树上查询。

因此，上述算法的总预处理复杂度是： $O (\frac{n}{\log n} \log n)$ 预处理倍增表， $O (n)$ 预处理梯子， $O (\sqrt{n} \log^{2} n)$ 预处理微树。每次查询，只需要讨论微树内部、微树跳到宏树上、宏树找叶子、叶子通过倍增跳到二进制最高位、在那个节点利用梯子信息求得答案，这是一个 $O (1)$ 的过程。因而我们有了一个 $⟨ O (n), O (1) ⟩$ 的 Level Ancestor 问题的解法。

代码

代码如下：

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

namespace
{
  using ui = unsigned int;

  namespace PRNG
  {
    ui s;

    ui get() {
      s ^= s << 13;
      s ^= s >> 17;
      s ^= s << 5;
      return s;
    }
  }

  struct HighBit
  {
    ui table[1024];

    HighBit() {
      table[0] = 0;
      table[1] = 0;
      for (ui i = 2; i < 1024; ++i) {
        table[i] = table[i >> 1] + 1;
      }
    }

    ui operator()(ui x) {
      if (x >> 20) return table[x >> 20] + 20;
      if (x >> 10) return table[x >> 10] + 10;
      return table[x];
    }

    ui operator[](ui x) {
      return 1 << operator()(x);
    }
  } highbit;

  ui concat(ui x, ui y) {
    if (y == 0) return x;
    return (x << (1 + highbit(y))) | y;
  }

  const int max_n = 555555;

  int n, q;
  int threshold;
  int parent[max_n];
  int dfn[max_n], dfa[max_n], dfr[max_n];
  int tme;
  int dep[max_n];
  int height[max_n];
  int preferred[max_n];
  int ladder_root[max_n];
  int *ladder_table[max_n];
  int siz[max_n];
  int *jump_table[max_n];
  bool is_jump_node[max_n];
  int any_jump_down[max_n];
  int micro_root[max_n];
  int micro_root_dis[max_n];
  ui shape[max_n];
  int dfs_stack[max_n];
  const int bit_size = 1 << 14;
  int **micro_table[bit_size];

  struct Graph
  {
    int beg[max_n], nxt[max_n], to[max_n];
    int e;

    void add_edge(int x, int y) {
      ++e;
      to[e] = y;
      nxt[e] = beg[x];
      beg[x] = e;
    }
  } g;

  void dfs(int x) {
    dfa[dfn[x] = ++tme] = x;
    dep[x] = dep[parent[x]] + 1;
    siz[x] = 1;
    height[x] = 0;
    for (int i = g.beg[x]; i; i = g.nxt[i]) {
      int y = g.to[i];
      dfs(y);
      siz[x] += siz[y];
      if (height[y] > height[x]) {
        height[x] = height[y];
        preferred[x] = y;
      }
    }
    ++height[x];
    dfr[x] = tme;
  }

  int cnt1 = 0, cnt2 = 0;

  int level_ancestor(int x, int k) {
    // out from micro tree
    if (micro_root[x] && k > micro_root_dis[x]) {
      k -= micro_root_dis[x] + 1;
      x = parent[micro_root[x]];
    }
    // on macro tree
    if (any_jump_down[x]) {
      k += dep[any_jump_down[x]] - dep[x];
      x = any_jump_down[x];
    }
    if (is_jump_node[x]) {
      if (k == 0) return x;
      x = jump_table[x][highbit(k)];
      k ^= highbit[k];
      int z = ladder_root[x];
      return ladder_table[z][dep[x] - k - dep[z]];
    }
    // on micro tree
    int z = micro_root[x];
    int **table = micro_table[shape[z]];
    return dfa[dfn[z] + table[dfn[x] - dfn[z]][k]];
  }
}

int main() {
  cin.sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> PRNG::s;
  int root = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> parent[i];
    g.add_edge(parent[i], i);
    if (parent[i] == 0) {
      root = i;
    }
  }
  threshold = log(n) / log(2) / 4 + 1;
  dfs(root);
  // calculate jump node
  memset(is_jump_node, 1, sizeof is_jump_node);
  for (int i = n; i >= 1; --i) {
    int x = dfa[i];
    if (siz[x] <= threshold) {
      is_jump_node[x] = false;
    } else {
      is_jump_node[parent[x]] = false;
    }
    if (is_jump_node[x]) {
      any_jump_down[x] = x;
    }
    if (any_jump_down[x]) {
      any_jump_down[parent[x]] = any_jump_down[x];
    }
  }
  // calculate jump table
  for (int i = 1; i <= n; ++i) {
    int x = dfa[i];

    dfs_stack[dep[x]] = x;
    if (is_jump_node[x]) {
      int len = highbit(dep[x] - 1) + 1;
      jump_table[x] = new int[len];
      for (int j = 0; j < len; ++j) {
        jump_table[x][j] = dfs_stack[dep[x] - (1 << j)];
      }
    }
  }
  // calculate the ladder info
  for (int i = 1; i <= n; ++i) {
    int x = dfa[i];

    dfs_stack[dep[x]] = x;
    int &z = ladder_root[x];
    if (x != preferred[parent[x]]) {
      z = x;

      ladder_table[x] = new int[height[x] * 2] + height[x];
      ladder_table[x][0] = x;
      for (int i = 1; i <= height[x] && i <= dep[x]; ++i) {
        ladder_table[x][-i] = dfs_stack[dep[x] - i];
      }
    } else {
      z = ladder_root[parent[x]];

      ladder_table[z][dep[x] - dep[z]] = x;
    }
  }
  // calculate micro tree info
  for (int i = n; i >= 1; --i) {
    int x = dfa[i];
    if (siz[x] <= threshold) {
      shape[x] <<= 1;
      shape[x] += highbit[shape[x]] << 1;
      if (siz[parent[x]] <= threshold) {
        shape[parent[x]] = concat(shape[x], shape[parent[x]]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    int x = dfa[i];
    if (micro_root[parent[x]]) {
      micro_root[x] = micro_root[parent[x]];
      micro_root_dis[x] = micro_root_dis[parent[x]] + 1;
    } else if (siz[x] <= threshold) {
      micro_root[x] = x;
      micro_root_dis[x] = 0;
    }
  }
  for (int i = 1; i <= n; ++i) {
    int x = dfa[i];
    if (micro_root[x] == x) {
      if (micro_table[shape[x]] != nullptr) {
        continue;
      }
      int **&table = micro_table[shape[x]];
      table = new int*[siz[x]];
      for (int j = dfn[x]; j <= dfr[x]; ++j) {
        int y = dfa[j];
        int len = dep[y] - dep[x];
        table[j - dfn[x]] = new int[len + 1];
        table[j - dfn[x]][0] = j - dfn[x];
        if (y != x) {
          int z = parent[y];
          memcpy(table[j - dfn[x]] + 1, table[dfn[z] - dfn[x]],
                 len * sizeof(int));
        }
      }
    }
  }
  // answer the queries
  unsigned long long ans = 0;
  int lastans = 0;
  for (int i = 1; i <= q; ++i) {
    int x = (PRNG::get() xor lastans) % n + 1;
    int k = (PRNG::get() xor lastans) % dep[x];
    int y = level_ancestor(x, k);
    lastans = y;
    ans ^= i * static_cast<unsigned long long>(y);
  }
  cout << ans << endl;
  // cleaning up
  for (int x = 1; x <= n; ++x) {
    if (jump_table[x] != nullptr)
      delete[] jump_table[x];
    if (ladder_table[x] != nullptr)
      delete[] (ladder_table[x] - height[x]);
  }
  for (int x = 1; x < (bit_size); ++x) {
    if (micro_table[x]) {
      int len = highbit(x) / 2;
      for (int i = 0; i < len; ++i) {
        delete[] micro_table[x][i];
      }
      delete[] micro_table[x];
    }
  }
  return 0;
}

EtaoinWu