警钟撅响(样例输出 15)
查看原帖
警钟撅响(样例输出 15)
589916
August_Light楼主2023/9/1 17:52

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) // here
                    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) // here
                    f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);
    }
}

因为 uu 必须取,所以要保证 j−k≥1j-k \ge 1。

2023/9/1 17:52
加载中...