POI Task Barricades

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

using namespace std;

const int INF = 1e5;

vector<vector<int>> g;
vector<vector<int>> costs;
/* for each node i, cost[i][k] is the minimum subtree edges that need to
be blocked to turn the subtree with root node i into a component of size k*/
void findCosts(int node = 1, int parent = 0) {
    costs[node] = {!!parent, 0};
    for (int child : g[node]) {
        if (child == parent) continue;
        findCosts(child, node);
        int a = (int)costs[node].size()-1, b = (int)costs[child].size()-1;
        // operations: a*b, result: a+=b
        vector<int> newCost(1+a+b, INF);
        newCost[0] = !!parent;
        for (int i = 1; i <= a; ++i) {
            for (int j = 0; j <= b; ++j) {
                newCost[i+j] = min(newCost[i+j], costs[node][i] + costs[child][j]);
            }
        }
        costs[node] = newCost;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    g.resize(1+n);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    costs.resize(1+n);
    findCosts();
    vector<int> minCost(1+n, INF); // to make a component of this size
    for (int i = 1; i <= n; ++i) {
        for (size_t k = 1; k < costs[i].size(); ++k) minCost[k] = min(minCost[k], costs[i][k] + (i != 1));
    }

    int m; cin >> m;
    while (m--) {
        int k; cin >> k;
        cout << minCost[k] << '\n'; // never impossible
    }
    return 0;
}