1272번: 특별 노드

https://www.acmicpc.net/problem/1272

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 1e3;
int n, r, a[MAX_N + 1];
vector<int> adj[MAX_N + 1];
vector<int> f(int h, int p) {
    vector<int> v(1, 0);
    for (auto it : adj[h]) {
        if (it == p) continue;
        vector<int> t = f(it, h), c(v.size() + t.size() - 1, 1e9);
        for (int i = 0; i<v.size(); i++)
            for (int j = 0; j < t.size(); j++)
                c[i + j] = min(c[i + j], v[i] + t[j]);
        v = c;
    }
    v.push_back(v.back() + a[h]);
    for (int i = v.size() - 2; i; i--) v[i] = v[i - 1] + a[h];
    v[0] += a[h];
    for (int i = 1; i < v.size(); i++) v[0] = min(v[0], v[i] - (i - 1)*a[h]);
    return v;
}
int main() {
    scanf("%d %d", &n, &r);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<int> v = f(r, -1);
    printf("%d", *min_element(v.begin(), v.end()));
    return 0;
}