USACO 2024 January Contest Silver Division - Potion Farming

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The number of traversals is equal to the number of leaves a tree has. I will claim that each leaf should be used together with the closest spawn point to the leaf.

This is pretty easy to prove as if we have a spawn point at that leaf, we should use it and if we don't use it, we will be worse off.

Now all we have to do is to do DFS from the root, add spawn points when they show up, remove them one by one (always the nearest one) at leaves and then just remove them when you can't use them anymore.

Source code

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

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

int n, spawn[100001], lf, oki[100001], cnt, is[100001], cntt[100001];
vector<vector<int> > tree;

vector<int> vx;

void dfs(int parent, int node) {
    while (oki[node]) {
        is[node]++;
        vx.push_back(node);
        oki[node]--;
    }

    bool leaf = 1;
    for (int i = 0; i < (int)tree[node].size(); i++) {
        int nxt = tree[node][i];
        if (nxt == parent) continue;
        dfs(node, nxt);
        leaf = 0;
    }

    if (leaf == 1 && !vx.empty()) {
        is[vx.back()]--;
        vx.pop_back();
        cnt++;
    }

    while (is[node]) {
        is[vx.back()]--;
        vx.pop_back();
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    tree.resize(n + 1);

    for (int i = 1; i <= n; i++) 
        cin >> spawn[i];

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    for (int i = 2; i <= n; i++)
        if (tree[i].size() == 1) 
            lf++;

    for (int i = 1; i <= lf; i++) 
        oki[spawn[i]]++;

    dfs(0, 1);
    cout << cnt;

    return 0;
}