USACO 2025 US Open Contest Silver Division - Ski Slope

Problem link: TBA

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem was by far the trickiest problem from this contest in the Silver division. I solved it by sorting the queries in increasing order of the weight and then I ran a DFS traversal to precompute all answers to queries as I went down the tree.

The main idea of my algorithm consists in knowing at each point the minimum skill required for a person to be able to go from a given node to the root by using at most \(i\) skips (that's how I will call the leaps of courage from now on). In order to update these things fast, we will use a multiset where we will remove the smallest values as we go down the tree, but in order to be able to keep using the same data structures later on in the problem too, we will undo the additions/removals as we go on different branches of the tree.

Last but not least, after we found these answers, we will keep all candidate answers in a 2D array named amnt and then have a prefix like traversal where we update the maximums based on the relative strength of the friends from the list of queries.

I recommend reading the source code carefully in order to understand the full idea, as additional comments can be found there too.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct info {
    int src, dest, d, e;
};

vector<vector<info>> tree;
vector<long long> ps, lvl;

void dfs (int node) {
    for (auto nxt : tree[node]) {
        int nw = nxt.dest;
        ps[nw] = ps[node] + nxt.e;
        lvl[nw] = lvl[node] + 1;
        dfs(nw);
    }
}

// here i want to find for every node what is the min skill level they need to make it to node with at most i skips
multiset<int> obstacles[11];
vector<vector<long long>> amnt; // amnt[i][j] = max answer if the strength would be equivalent to the one from jth query and you can make i mistakes 
vector<pair<int, pair<int, int>>> qvals;

void dfs2 (int node, vector<int> minvals) {
    vector<int> minvals2 = minvals;
    for (int i = 0; i <= 10; i++) {
        int L = 0;
        int R = (int) qvals.size() - 1;
        int ans = (int) qvals.size();
        while (L <= R) {
            int mid = (L + R) / 2;
            if (qvals[mid].first >= minvals[i]) {
                ans = mid;
                R = mid - 1;
            }
            else {
                L = mid + 1;
            }
        }
        if (ans != (int) qvals.size()) {
            amnt[i][ans] = max(amnt[i][ans], ps[node]);
        }
    }
    for (int i = 0; i < (int) tree[node].size(); i++) {
        int nxt = tree[node][i].dest;
        for (int pos = 0; pos <= 10; pos++) {
            obstacles[pos].insert(tree[node][i].d);
        }
        vector<int> removals(11, -1);
        for (int pos = 0; pos <= 10; pos++) {
            while ((int) obstacles[pos].size() > pos) {
                removals[pos] = *obstacles[pos].begin();
                obstacles[pos].erase(obstacles[pos].lower_bound(removals[pos]));
            }
            minvals[pos] = max(minvals[pos], removals[pos]);
        }
        dfs2(nxt, minvals);
        for (int pos = 0; pos <= 10; pos++) {
            if (removals[pos] != -1) {
                obstacles[pos].insert(removals[pos]);
            }
        }
        minvals = minvals2;
        for (int pos = 0; pos <= 10; pos++) {
            if (obstacles[pos].find(tree[node][i].d) != obstacles[pos].end()) {
                obstacles[pos].erase(obstacles[pos].lower_bound(tree[node][i].d));
            }
        }
    }
}
void solve () {
    int n;
    cin >> n;

    vector<int> parent(n+1);
    vector<info> data(n);
    tree.resize(n+1), ps.resize(n+1); lvl.resize(n+1);

    for (int i = 2; i <= n; i++) {
        cin >> data[i-1].src >> data[i-1].d >> data[i-1].e;
        data[i-1].dest = i;
        parent[i] = data[i-1].src;
        tree[data[i-1].src].push_back(data[i-1]);
    }


    dfs(1);

    int q;
    cin >> q;

    qvals.resize(q);
    for (int i = 0; i < q; i++) {
        cin >> qvals[i].first >> qvals[i].second.first;
        qvals[i].second.second = i;
    }
    sort(qvals.begin(), qvals.end());

    vector<long long> ans(q);
    vector<int> mx(11);
    amnt.resize(11, vector<long long> (q+1));
    dfs2(1, mx); 

    for (int j = 0; j < q; j++) {
        if (j > 0) {
            for (int i = 0; i <= 10; i++) { 
                amnt[i][j] = max(amnt[i][j], amnt[i][j-1]);
            }
        }
        ans[qvals[j].second.second] = amnt[qvals[j].second.first][j];
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}