USACO Cowflix (slow)

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

using namespace std;

const int INF = 1e9;

string s;
vector<vector<int>> g;

vector<int> minCostInclusive, minCost; // inclusive/exclusive <- whether node is / is not in a component
vector<int> minCostInclusiveM, minCostM; // optimal number of components
void dfs(int node, int k, int par = -1) {
    minCostInclusive[node] = k+1, minCostInclusiveM[node] = 1;
    minCost[node] = 0, minCostM[node] = 0;
    for (int child : g[node]) {
        if (child == par) continue;
        dfs(child, k, node);
        if (minCost[child] < minCostInclusive[child] - k) {
            minCostInclusive[node] += minCost[child],
            minCostInclusiveM[node] += minCostM[child];
        } else {
            minCostInclusive[node] += minCostInclusive[child] - k;
            minCostInclusiveM[node] += minCostInclusiveM[child] - 1;
        }
        minCost[node] += minCost[child], minCostM[node] += minCostM[child];
    }
    if (s[node] == '0') { // take min of inclusive and exclusive
        pair<int, int> mn = min(pair<int, int>{minCost[node], minCostM[node]}, {minCostInclusive[node], minCostInclusiveM[node]});
        minCost[node] = mn.first, minCostM[node] = mn.second;
    }
    else minCost[node] = minCostInclusive[node], minCostM[node] = minCostInclusiveM[node];
}

vector<int> c, m; // for a certain k: cost, optimal number of components
void fillIn(int k) {
    dfs(0, k);
    c[k] = minCost[0], m[k] = minCostM[0];
}

void divideAndConquer(int l, int r) {
    if (m[l-1] == m[r+1]) {
        for (int i = l; i <= r; ++i) {
            m[i] = m[i-1];
            c[i] = c[i-1] + m[i-1];
        }
    } else if (l <= r) {
        int i = (l + r) / 2;
        fillIn(i);
        divideAndConquer(l, i-1);
        divideAndConquer(i+1, r);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n >> s;
    g.resize(n);
    for (int i = 0; i < n-1; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    minCostInclusive = minCost = minCostInclusiveM = minCostM = vector<int>(n);
    c = m = vector<int>(1+n+1);
    m[0] = n+1, m[n+1] = 0;
    divideAndConquer(1, n);
    for (int k = 1; k <= n; ++k) cout << c[k] << '\n';
    return 0;
}