【模板】树上 K 级祖先

GitHub跳转原题关系图返回列表

预处理每个点的 2^j 级祖先，把每次 K 级祖先查询转化为二进制跳跃。

OJ: luogu

题目 ID: P5903

难度:普及+/提高

标签:树倍增LCA

日期: 2026-06-22 22:33

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一棵有根树。每次询问点 x 的 k 级祖先，也就是从 x 沿父亲指针向上走 k 步到达的点。

本题的询问由随机函数和上一次答案在线生成。最终输出所有 i * ans_i 的异或和。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：逐层爬父亲回答 K 级祖先，只适合小数据对拍。

typedef unsigned int ui;

const int MAXN = 2005;

int n, q;
ui seed_value;
int parent_node[MAXN];
int depth_node[MAXN];
vector<int> children[MAXN];
int root_node;

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

void dfs_depth(int u) {
    for (int i = 0; i < (int)children[u].size(); i++) {
        int v = children[u][i];
        depth_node[v] = depth_node[u] + 1;
        dfs_depth(v);
    }
}

int kth_ancestor_brute(int x, int k) {
    while (k > 0) {
        x = parent_node[x];
        k--;
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q >> seed_value;
    for (int i = 1; i <= n; i++) {
        cin >> parent_node[i];
        if (parent_node[i] == 0) {
            root_node = i;
        } else {
            children[parent_node[i]].push_back(i);
        }
    }

    depth_node[root_node] = 1;
    dfs_depth(root_node);

    int last_answer = 0;
    unsigned long long final_answer = 0;
    for (int i = 1; i <= q; i++) {
        int x = (int)(((get(seed_value) ^ (ui)last_answer) % (ui)n) + 1);
        int k = (int)((get(seed_value) ^ (ui)last_answer) % (ui)depth_node[x]);
        int current_answer = kth_ancestor_brute(x, k);
        last_answer = current_answer;
        final_answer ^= 1ULL * (unsigned int)i * (unsigned int)current_answer;
    }

    cout << final_answer << '\n';

    return 0;
}

朴素做法是每次沿父亲指针爬 k 步。询问数量很大，不能逐层爬。

预处理倍增祖先：

text
up[x][j] = x 的 2^j 级祖先

转移：

text
up[x][j] = up[ up[x][j-1] ][j-1]

查询时，把 k 拆成二进制。若第 j 位为 1，就让 x 跳到 up[x][j]。所有这些跳跃步数之和正好是 k，最后的点就是答案。

本题还有两个实现细节：

  • 输入给出的是每个点的父亲，父亲为 0 的点是根；
  • 询问要按题面公式在线生成，并用上一次答案参与异或。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

typedef unsigned int ui;

const int MAXN = 500005;
const int LOG = 20;

int n, q;
ui seed_value;
int parent_node[MAXN];
int head[MAXN], to[MAXN], nxt[MAXN], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG + 1];
int root_node;

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

void add_child(int parent, int child) {
    edge_cnt++;
    to[edge_cnt] = child;
    nxt[edge_cnt] = head[parent];
    head[parent] = edge_cnt;
}

void read_input() {
    cin >> n >> q >> seed_value;
    for (int i = 1; i <= n; i++) {
        cin >> parent_node[i];
        if (parent_node[i] == 0) {
            root_node = i;
        } else {
            add_child(parent_node[i], i);
        }
    }
}

void build_ancestor() {
    queue<int> que;
    depth_node[root_node] = 1;
    up[root_node][0] = 0;
    que.push(root_node);

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int j = 1; j <= LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            depth_node[v] = depth_node[u] + 1;
            up[v][0] = u;
            que.push(v);
        }
    }
}

int kth_ancestor(int x, int k) {
    for (int j = 0; j <= LOG; j++) {
        if ((k & (1 << j)) != 0) {
            x = up[x][j];
        }
    }
    return x;
}

void solve() {
    build_ancestor();

    int last_answer = 0;
    unsigned long long final_answer = 0;

    for (int i = 1; i <= q; i++) {
        int x = (int)(((get(seed_value) ^ (ui)last_answer) % (ui)n) + 1);
        int k = (int)((get(seed_value) ^ (ui)last_answer) % (ui)depth_node[x]);
        int current_answer = kth_ancestor(x, k);
        last_answer = current_answer;
        final_answer ^= 1ULL * (unsigned int)i * (unsigned int)current_answer;
    }

    cout << final_answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

预处理 O(nlogn)O(n log n)，每次询问 O(logn)O(log n)。

空间复杂度为 O(nlogn)O(n log n)。

总结

K 级祖先是倍增最直接的应用。

只要预处理好 2^j 级祖先，就可以把任意向上跳 k 步拆成若干次二进制跳跃。