分析

非常不错的一道树形 。定义 以 为根节点，其他的节点就深度 的最优答案。那么我们有转移 。那么当 时，我们有一下转移 。那么答案是 就好了，总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
const int N = 210;
int f[N][N],a[N],n,k;
vector<int> G[N];
void dfs(int x,int fa) {
    f[x][0] = a[x];
//    cout << x << " " << fa << endl;
    for(auto y : G[x]) if(y ^ fa) dfs(y,x);
    for(auto y : G[x]) if(y ^ fa) f[x][0] += f[y][k];
    for(int i = 1;i < n;i++) {
        for(auto y : G[x]) {
            if(y == fa) continue;
            int cnt = f[y][i - 1];
            for(auto z : G[x]) {
                if(z == fa || z == y) continue;
                cnt += f[z][max(i - 1,k - i)];
            }
            f[x][i] = max(f[x][i],cnt);
        }
    }
    for(int i = n - 1;i >= 0;i--) f[x][i] = max(f[x][i + 1],f[x][i]);
}
int main() {
    n = read();k = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        G[a].push_back(b);G[b].push_back(a);
    }
    dfs(1,0);
    cout << f[1][0] << endl;
}