【模板】树上 K 级祖先

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

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

OJ: luogu

题目 ID: P5903

难度:提高+/省选-

标签:树倍增LCA

创建: 2026-06-22 22:33

更新: 2026-08-09 06:46

后置题目

luogu P1967[NOIP 2013 提高组] 货车运输B 的倍增查询直接复用 A 教的 up[x][j] 倍增表与按二进制拆分上跳，只是上跳时沿途对 min_edge 取最小值，以回答路径瓶颈查询 roj 3192Freda的传呼机B 的圆方树做法在方点 LCA 分支里用 up_k 沿倍增表上跳，取 x、y 向上跳到方点的两个儿子 ax、ay，正是 A 教的「2^j 级祖先 + 二进制拆分逐位上跳」这一步；A 只做单点 K 级祖先，B 把它嵌进仙人掌缩环建圆方树之后再叠加环内取短弧。roj 3600[NOIP2012-提高] 开车旅行B 的按轮倍增表与求 k 级祖先完全同构：把 A 的 up[x][j]=up[up[x][j-1]][j-1] 前半段落点拼后半段换成 g[k][i]=g[k-1][g[k-1][i]]，同一步再用于二进制拆分跳跃；差异只是 B 的跳跃代价带权并需从高到低贪心。roj 3155「Count The Repetitions」计算重复B 的确定性转移表沿用 A 的倍增表自拼方式（up[k]=up[k-1] 在状态上自拼），再用二进制拆分挑选，只是把「跳 k 步」换成「走 2^k 份 s2」，新增难度在贪心压缩与占用份数判据 roj 1554「一本通 4.4 例 3」异象石B 的 dist 每次操作要调用 3 次 LCA，其倍增 LCA 正是直接复用 A 教的「预处理 2^j 级祖先倍增表」这一步（jump[k][v] 与 up[x][j] 同构），A 是纯模板、B 在此之上叠加 DFS 序成环恒等式与有序表增量维护，构成 delta=2 的台阶。luogu P9235[蓝桥杯 2023 省 A] 网络稳定性B 查询第一步「把深的点提到同一层」正是执行 A 教的「k 拆二进制沿 up 表逐位跳 k 级祖先」这一步（这里 k 即深度差），只是沿跳更新最小边权，再叠加 A 未教的同步上跳收尾与最大生成森林建树。luogu P4427[BJOI2018] 求和B 的前缀和拆分公式依赖 p=lca(x,y)，求 p 时复用 A 教的倍增表 up[x][j] 预处理与按二进制拆分上跳步骤，B 在此之上叠加 depth^k 前缀和预处理与容斥拆路径。

题意

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

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

思路

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

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#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

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

转移：

text

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

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

本题还有两个实现细节：

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#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(n log n)$ ，每次询问 $O(log n)$ 。

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

总结

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

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

P5903 【模板】树上 K 级祖先

题目背景

本题仅作为长链剖分求树上 $k$ 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。

题目描述

给定一棵 $n$ 个点的有根树。

有 $q$ 次询问，第 $i$ 次询问给定 $x_i, k_i$ ，要求点 $x_i$ 的 $k_i$ 级祖先，答案为 $ans_i$ 。特别地， $ans_0 = 0$ 。

本题中的询问将在程序内生成。

给定一个随机种子 $s$ 和一个随机函数 $\operatorname{get}(x)$ ：

cpp

1
2
3
4
5
6
7
8
9#define ui unsigned int
ui s;

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

你需要按顺序依次生成询问。

设 $d_i$ 为点 $i$ 的深度，其中根的深度为 $1$ 。

对于第 $i$ 次询问， $x_i = ((\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod n) + 1$ ， $k_i = (\operatorname{get}(s) \operatorname{xor} ans_{i-1}) \bmod d_{x_i}$ 。

输入格式

第一行三个整数 $n, q, s$ 。

第二行 $n$ 个整数 $f_{1\dots n}$ ，其中 $f_i$ 表示 $i$ 的父亲。特别地，若 $f_i = 0$ ，则 $i$ 为根。

输出格式

一行一个整数，表示 $\operatorname{xor}_{i=1}^q i \times ans_i$ 。

输入输出样例 #1

输入 #1

text

1
26 3 7
5 5 2 2 0 3

输出 #1

text

说明/提示

【样例说明】

$x_1 = 4$ ， $k_1 = 1$ ， $ans_1 = 2$ ；
$x_2 = 6$ ， $k_2 = 3$ ， $ans_2 = 5$ ；
$x_3 = 3$ ， $k_3 = 0$ ， $ans_3 = 3$ ；
故输出 $1$ 。

对于 $20\%$ 的数据， $n,q \le 10^3$ 。

对于 $50\%$ 的数据， $n,q \le 10^5$ 。

对于 $100\%$ 的数据， $2 \le n \le 5 \times 10^5$ ， $1 \le q \le 5 \times 10^6$ ， $1 \le s < 2^{32}$ 。

【模板】树上 K 级祖先

目录

题意

思路

代码

复杂度

总结