题解 P5903 【【模板】树上 k 级祖先】
xht
2020-01-07 18:30:01
长链剖分的经典应用。
显然这个问题有 $\mathcal O(n \log n) - \mathcal O(\log n)$ 的树上倍增做法，然而还不够优秀。
首先我们进行预处理：
1. 对树进行长链剖分，记录每个点所在链的顶点和深度，$\mathcal O(n)$。
2. 树上倍增求出每个点的 $2^n$ 级祖先，$\mathcal O(n \log n)$。
3. 对于每条链，如果其长度为 $len$，那么在顶点处记录顶点向上的 $len$ 个祖先和向下的 $len$ 个链上的儿子，$\mathcal O(n)$。
4. 对 $i \in [1, n]$ 求出在二进制下的最高位 $h_i$，$\mathcal O(n)$。
对于每次询问 $x$ 的 $k$ 级祖先：
1. 利用倍增数组先将 $x$ 跳到 $x$ 的 $2^{h_k}$ 级祖先，设剩下还有 $k^{\prime}$ 级，显然 $k^{\prime} < 2^{h_k}$，因此此时 $x$ 所在的长链长度一定 $\ge 2^{h_k} > k^{\prime}$。
2. 由于长链长度 $ > k^{\prime}$，因此可以先将 $x$ 跳到 $x$ 所在链的顶点，若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。
这样时间复杂度为 $\mathcal O(n \log n) - \mathcal O(1)$ 的。
```cpp
const int N = 5e5 + 7;
int n, q, rt, g[N], d[N], f[N][21], son[N], dep[N], top[N], ans;
vi e[N], u[N], v[N];
ui s;
ll Ans;
inline ui get(ui x) {
return x ^= x << 13, x ^= x >> 17, x ^= x << 5, s = x;
}
void dfs(int x) {
dep[x] = d[x] = d[f[x][0]] + 1;
for (auto y : e[x]) {
f[y][0] = x;
for (int i = 0; f[y][i]; i++) f[y][i+1] = f[f[y][i]][i];
dfs(y);
if (dep[y] > dep[x]) dep[x] = dep[y], son[x] = y;
}
}
void dfs(int x, int p) {
top[x] = p;
if (x == p) {
for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
u[x].pb(o), o = f[o][0];
for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
v[x].pb(o), o = son[o];
}
if (son[x]) dfs(son[x], p);
for (auto y : e[x]) if (y != son[x]) dfs(y, y);
}
inline int ask(int x, int k) {
if (!k) return x;
x = f[x][g[k]], k -= 1 << g[k], k -= d[x] - d[top[x]], x = top[x];
return k >= 0 ? u[x][k] : v[x][-k];
}
int main() {
rd(n), rd(q), rd(s), g[0] = -1;
for (int i = 1; i <= n; i++)
rd(f[i][0]), e[f[i][0]].pb(i), g[i] = g[i>>1] + 1;
rt = e[0][0], dfs(rt), dfs(rt, rt);
for (int i = 1, x, k; i <= q; i++) {
x = (get(s) ^ ans) % n + 1;
k = (get(s) ^ ans) % d[x];
Ans ^= 1ll * i * (ans = ask(x, k));
}
print(Ans);
return 0;
}
```