IOI '10 P6 - Traffic Congestion (Standard I/O)

#include <iostream>
#include <vector>

using namespace std;

const int INF = 2e9 + 1e8;

vector<vector<int>> g;
vector<int> p, subtree, par;
int dfs(int node, int parent = -1) {
    par[node] = parent;
    subtree[node] = p[node];
    for (int child : g[node]) {
        if (child != parent) subtree[node] += dfs(child, node);
    }
    return subtree[node];
}

int main() {
    int n; cin >> n;
    p.resize(n);
    for (int &x : p) cin >> x;
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    subtree.resize(n), par.resize(n);
    int total = dfs(0);
    pair<int, int> best{INF, INF};
    for (int i = 0; i < n; ++i) {
        int maxEdge = 0;
        for (int child : g[i]) {
            if (child == par[i]) maxEdge = max(maxEdge, total-subtree[i]);
            else maxEdge = max(maxEdge, subtree[child]);
        }
        best = min(best, {maxEdge, i});
    }
    cout << best.second << endl;
    return 0;
}