很早之前写过两篇线性时间的 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=\frac{\log n}{4}\) 。我们称一个节点是宏节点，表示其子树大小 \(> 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;
}