线性时间 Level Ancestor 问题

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

The Problem

所谓 Level Ancestor 问题 \(\mathrm{LA}(x,k)\) ,是形如这样的询问:

\(x\) 这个点的 \(k\) 级祖先是谁?

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

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

The Solution

Trick 1, Path Decomposition

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

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

Trick 2, Binary Lifting

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

Trick 3, Ladders

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

Trick 4, Mo4R

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

设 $ k = $ 。我们称一个节点是宏节点,表示其子树大小 \(> k\) ;否则称其为微节点

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

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

因此,上述算法的总预处理复杂度是: \(O\left( \frac{n}{\log n}\log n \right)\) 预处理倍增表, \(O\left( n \right)\) 预处理梯子, \(O\left( \sqrt{n}\log^{2}n \right)\) 预处理微树。每次查询,只需要讨论微树内部、微树跳到宏树上、宏树找叶子、叶子通过倍增跳到二进制最高位、在那个节点利用梯子信息求得答案,这是一个 \(O\left( 1 \right)\) 的过程。因而我们有了一个 \(\left\langle O\left( n \right), O\left( 1 \right) \right\rangle\) 的 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;
}