咕咕树

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

const int MAXN = 5005;

int n, l;
int a[MAXN];
vector<int> G[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];

void dfs(int u, int fa) {
    for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = *it;
        if (v == fa) continue;
        dfs(v, u);
        for (int i = 0; i < l; ++i)
            g[u][i] += f[v][i];
    }
    for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = *it;
        if (v == fa) continue;
        for (int i = 1; i < l; ++i) {
            f[u][i] = min(f[u][i], g[u][min(i - 1, l - i - 1)] - f[v][min(i - 1, l - i - 1)] + f[v][i - 1]);
        }
    }
    f[u][0] = a[u] + g[u][l - 1];
    if (u != 1 && G[u].size() == 1) f[u][1] = 0;
    for (int i = 1; i < l; ++i)
        f[u][i] = min(f[u][i], f[u][i - 1]);
}

int main() {
    int sum = 0;
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), sum += a[i];
    if (l == 0) return printf("%d", sum), 0;
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    printf("%d", f[1][l - 1]);
    return 0;
}