暴力每个点作为根节点都重新算一遍

70 分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, k;
vector<int> e[MAXN + 5];
int c[MAXN + 5];
int dfs(int u, int fa, int dep)
{
    int ans = c[u];
    if (dep == 0)
        return ans;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        ans += dfs(v, u, dep - 1);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
        cout << dfs(i, 0, k) << "\n";
    return 0;
}

40 分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXK = 20;
int n, k;
vector<int> e[MAXN + 5];
int c[MAXN + 5];
int f[MAXN + 5][MAXK + 5];
void dfs(int u, int fa)
{
    for (int i = 0; i <= k; i++)
        f[u][i] = c[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        for (int i = 1; i <= k; i++)
            f[u][i] += f[v][i - 1];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
    {
        dfs(i, 0);
        cout << f[i][k] << "\n";
    }
    return 0;
}

换根 dp

f[u][i] = dp[u][i] + f[fa][i-1] - dp[u][i-2];

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXK = 20;
int n, k;
vector<int> e[MAXN + 5];
int c[MAXN + 5];
// dp[u][i] u 子树中，距离 u 在 i 以内的点权和
int dp[MAXN + 5][MAXK + 5];
void dfs(int u, int fa)
{
    for (int i = 0; i <= k; i++)
        dp[u][i] = c[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        for (int i = 1; i <= k; i++)
            dp[u][i] += dp[v][i - 1];
    }
}
// f[u][i] u 作为根节点时，距离 u 在 i 以内的点权和
int f[MAXN + 5][MAXK + 5];
void dfs2(int u, int fa)
{
    for (int i = 0; i <= k; i++)
    {
        // 计算 f[u][i]
        f[u][i] = dp[u][i];
        if (fa != 0 && i >= 1)
            f[u][i] += f[fa][i - 1];
        if (fa != 0 && i >= 2)
            f[u][i] -= dp[u][i - 2];
    }
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs2(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    dfs(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        cout << f[i][k] << "\n";
    return 0;
}