Ski Slope (USACO Silver 2025 Open)

这个题知识点不难，只是实现上有一些繁琐。

首先，比较容易看出来，这是一棵以1号点为根的树，树上的每条边都有（技能值skill，快乐值enjoyment）属性。如果从一个节点出发能够到达根，那么路上所有快乐值的和就是结果，一个固定的节点出发的快乐值也是固定的。

所以问题转化成，对于每个朋友，根据技能值和勇气值，怎样快速计算出从哪些节点出发能够到达根，以及最大的快乐值是多少。

Naive的算法是 $\mathcal{O}(N^2)$ 复杂度的。这里关键在于注意到勇气值小于等于10，所以只有11种可能性。因此我们可以在预处理时，只保留需要的勇气值不超过10的结果，舍弃无用状态。对每个节点的每种勇气水平（共11种），预处理出到达根节点所需的最小技能值。这里可以自顶向下递归DFS，每个节点根据父节点的状态和边的信息计算出自己的结果（一个简单的树上DP）。对于每个勇气值，整理所有（最小技能skill，快乐值enjoyment）对，去掉所有非最优解（简单通过排序就可以），保证每个技能值下的快乐最大。

有了这个预处理的结果之后，对于每个朋友，都可以在相应勇气数组的（skill, enjoyment）列表中二分查找，就可快速得到最大快乐值的答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
vector<int> adj[100005];
int d[100005], ci[100005];     // difficulty, enjoyment
int ms[100005][11];            // min skill required to reach waypoint 1 with courage level i
ll e[100005];                  // total enjoyment from waypoint i
vector<pair<int,ll>> res[11];  // <skill, enjoyment> pairs for each courage
vector<pair<int,ll>> res2[11]; // optimal <skill, enjoyment> pairs
int skill, c;                  // skill, courage
 
// compute ms
void dfs(int x, int p) {
    e[x] = e[p] + ci[x];
    if (p) {
        for (int i = 0; i <= 10; i++) {
            if (ms[p][i] >= d[x])
                ms[x][i] = ms[p][i];
            else if (i > 0)
                ms[x][i] = min(ms[p][i-1], d[x]);
            else
                ms[x][i] = d[x];
            
            res[i].push_back({ms[x][i], e[x]});
        }
    }
 
    for (int i : adj[x]) {
        dfs(i, x);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int p;
        scanf("%d %d %d", &p, &d[i], &ci[i]);
        adj[p].push_back(i);
    }
    dfs(1, 0);                          // compute min skill for each courage from each node
 
    for (int i = 0; i <= 10; i++) {     // remove all non-optimal pairs
        res[i].push_back({0, 0});
        sort(res[i].begin(), res[i].end());
        ll mx = -1;
        for (auto p : res[i]) {
            if (p.s > mx) {
                if (res2[i].size() > 0 && res2[i].back().f == p.f)
                    res2[i].pop_back();
                mx = p.s;
                res2[i].push_back(p);
            }
        }
    }
 
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {      // binary search for results
        scanf("%d %d", &skill, &c);
        if (res2[c].size() == 0) {
            printf("0\n");
            continue;
        }
        auto it = upper_bound(res2[c].begin(), res2[c].end(), make_pair(skill, 0LL));  // it >= s[i]
        if (it == res2[c].end() || it->f > skill)
            it--;
        printf("%lld\n", it->s);        
    }
 
    return 0;
}