NO:
void dfs(int u, int fa) {
f[u][1] = a[u];
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
for (int j = m; j >= 0; j--)
for (int k = 0; k <= m; k++)
if (j-k >= 0)
f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);
}
}
YES:
void dfs(int u, int fa) {
f[u][1] = a[u];
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
for (int j = m; j >= 0; j--)
for (int k = 0; k <= m; k++)
if (j-k >= 1)
f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);
}
}
因为 u 必须取,所以要保证 j−k≥1。