Ski Slope

题意

山上的标记点形成一棵以 1 为根的树。每个点 i > 1 有一条边通向父亲 p_i，这条边有：

难度 d_i；
乐趣值 e_i。

一次滑雪会选择一个起点，然后沿父亲方向一直滑到 1。总乐趣是路径上所有 e_i 的和。

每个询问给出技能值 s 和勇气值 c，要求选择一条从某个点到根的路径，使路径上难度大于 s 的边最多有 c 条，并最大化总乐趣。

思路

先看一个最直接的暴力：每个询问枚举所有起点，再沿父链检查这条路径是否合法。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:31
 * update_at: 2026-07-11 20:32
 */
// brute.cpp：小数据暴力解，每个询问枚举所有起点并沿父链检查。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n, m;
int parent_node[MAXN];
int difficulty[MAXN];
ll enjoyment[MAXN];

ll calc_path(int start, int skill, int courage) {
    int bad = 0;
    ll sum = 0;

    int u = start;
    while (u != 1) {
        if (difficulty[u] > skill) {
            bad++;
        }
        sum += enjoyment[u];
        u = parent_node[u];
    }

    if (bad <= courage) return sum;
    return -1;
}

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

    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i] >> difficulty[i] >> enjoyment[i];
    }

    cin >> m;
    for (int i = 1; i <= m; i++) {
        int skill, courage;
        cin >> skill >> courage;

        ll ans = 0;
        for (int start = 1; start <= n; start++) {
            ll value = calc_path(start, skill, courage);
            if (value > ans) ans = value;
        }
        cout << ans << '\n';
    }

    return 0;
}

这个暴力的瓶颈很明显：每个询问都要枚举所有点，并且还要沿父链向上走，最坏会接近 $O(MN^2)$ 。

观察勇气值的范围： $0\leqslant c\leqslant 10$ 。

对一条路径来说，如果我们知道这条路径上最大的 11 条边难度，查询时就够用了：

$c = 0$ ：要求第 1 大难度 $<= s$ ；
$c = 1$ ：允许 1 条边超过 s，要求第 2 大难度 $<= s$ ；
$c = 10$ ：允许 10 条边超过 s，要求第 11 大难度 $<= s$ 。

所以对于每个点 i，预处理：

sum_enjoy[i]：从 i 滑到 1 的总乐趣；
top_diff[i][0..10]：从 i 到 1 的路径上前 11 大难度，按从大到小排列；不足 11 条时用 -1 补齐。

由于题目保证 p_i < i，可以按编号从小到大计算。点 i 的前 11 大难度只可能来自：

text

1父亲 p_i 的前 11 大难度 + 当前边 d_i

把 d_i 插入父亲的有序数组中，保留前 11 个即可。

样例中的路径信息如下：

起点	路径难度	总乐趣	前 2 大难度
1	空	0	`-1, -1`
2	`20`	200	`20, -1`
3	`30, 20`	500	`30, 20`
4	`10, 20`	300	`20, 10`

例如查询 $s=19, c=1$ ，要求第 2 大难度 $<= 19$ 。点 4 的第 2 大难度是 10，合法，乐趣为 300；点 3 的第 2 大难度是 20，不合法。

接下来要快速回答最大乐趣。

对每个 c 单独建一张表：

text

1(top_diff[i][c], sum_enjoy[i])

按第一维排序后，再把第二维改成前缀最大值。这样对于查询 (s,c)，只要二分找到最后一个 $top_diff <= s$ 的位置，这个位置的前缀最大值就是答案。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:31
 * update_at: 2026-07-11 20:32
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MAXC = 11;

int n, m;
int parent_node[MAXN];
int difficulty[MAXN];
ll enjoyment[MAXN];
ll sum_enjoy[MAXN];               // sum_enjoy[i] 表示从 i 滑到 1 的总乐趣
int top_diff[MAXN][MAXC];         // top_diff[i][k] 表示路径上第 k+1 大难度
pair<int, ll> info[MAXC][MAXN];   // 对每个 c 存 (第 c+1 大难度, 总乐趣)

void insert_difficulty(int node, int value) {
    for (int i = 0; i < MAXC; i++) {
        top_diff[node][i] = top_diff[parent_node[node]][i];
    }

    for (int i = 0; i < MAXC; i++) {
        if (value > top_diff[node][i]) {
            for (int j = MAXC - 1; j > i; j--) {
                top_diff[node][j] = top_diff[node][j - 1];
            }
            top_diff[node][i] = value;
            break;
        }
    }
}

void build_tables() {
    for (int c = 0; c < MAXC; c++) {
        for (int i = 1; i <= n; i++) {
            info[c][i] = make_pair(top_diff[i][c], sum_enjoy[i]);
        }

        sort(info[c] + 1, info[c] + n + 1);

        for (int i = 2; i <= n; i++) {
            if (info[c][i].second < info[c][i - 1].second) {
                info[c][i].second = info[c][i - 1].second;
            }
        }
    }
}

ll answer_query(int skill, int courage) {
    pair<int, ll> target = make_pair(skill + 1, -1LL);
    pair<int, ll> *it = lower_bound(info[courage] + 1, info[courage] + n + 1, target);
    int pos = (int)(it - info[courage]) - 1;
    return info[courage][pos].second;
}

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

    cin >> n;

    for (int i = 0; i < MAXC; i++) {
        top_diff[1][i] = -1;
    }
    sum_enjoy[1] = 0;

    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i] >> difficulty[i] >> enjoyment[i];
        sum_enjoy[i] = sum_enjoy[parent_node[i]] + enjoyment[i];
        insert_difficulty(i, difficulty[i]);
    }

    build_tables();

    cin >> m;
    for (int i = 1; i <= m; i++) {
        int skill, courage;
        cin >> skill >> courage;
        cout << answer_query(skill, courage) << '\n';
    }

    return 0;
}

复杂度

每个点只维护 11 个难度，预处理前 11 大难度为 $O(11N)$ 。

对每个 c 排序一次，共 11 次，复杂度为 $O(11N\log N)$ 。

每个询问二分一次，复杂度为 $O(\log N)$ 。

总时间复杂度为 $O(11N\log N+M\log N)$ ，空间复杂度为 $O(11N)$ 。

总结

这题的关键是抓住 $c\leqslant 10$ 。

路径上有很多边，但查询只关心“超过技能值的边有多少条”，所以保留前 11 大难度就能覆盖所有勇气值。之后把每个勇气值对应的限制单独排序，就把树上路径查询转成了普通的二分前缀最大值查询。

目录

题意

思路

代码

复杂度

总结