Codeforces 1249 #Codeforces

1249F.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 200 + 10;

int weight[maxn];
vector<int> G[maxn];
int dp[maxn][maxn];
int n, k;

void dfs(int u, int fa){
    for(int v:G[u]){
        if(v != fa) dfs(v, u);
    }
    dp[u][0] = weight[u];
    for(int v:G[u]){
        if(v != fa) dp[u][0] += dp[v][k - 1];
    }
    for(int dep=1; dep<=n; dep++){
        int ans = 0;
        for(int other:G[u]){
            if(other == fa) continue;
            int tmp_ans = dp[other][dep-1];
            for(int v:G[u]){
                if(v == fa || v == other) continue;
                tmp_ans += dp[v][max(dep - 1, k - 1 - dep)];
            }
            ans = max(ans, tmp_ans);
        }
        dp[u][dep] = ans;
    }

    for(int i=n; i>0; i--) dp[u][i-1] = max(dp[u][i-1], dp[u][i]);
}

void solve(){
    memset(dp, 0, sizeof dp);
    
    cin >> n >> k;
    k++;
    for(int i=1; i<=n; i++) cin >> weight[i];
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    cout << dp[1][0] << '\n';
}

signed main(){
    Android;
    solve();
}