题解 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) 的。

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;
}