"常见"树上背包优化技巧

· · 个人记录

题意:给你一颗树,每个点有一个权值,每条边可以留下或删除,问有多少种方案使得1所在的连通块中所有点的权值和恰好为 K.

暴力 n^3:

int dfs(int u, int fa) {
    sum[u] = val[u];
    dp[u][val[u]] = 1;
    for (int i = head[u]; i; i = edges[i].nex) {
        int v = edges[i].to;
        if (v == fa) continue;
        dfs(v, u);
        sum[u] += sum[v];
        for (int j = min(sum[u], K); j >= val[u]; --j) {
            dp[u][j] = 1ll*dp[u][j]*(1+dp[v][0])%mod;
            for (int k = max(1, val[v]); k <= min(sum[v], j-val[u]); ++k)
                (dp[u][j] += 1ll*dp[u][j-k]*dp[v][k]%mod) %= mod;
        }
    }
}

"常见"优化技巧:

```cpp void dfs(int u, int fa) { siz[u] = 1; for (int i = head[u]; i; i = edges[i].nex) { int v = edges[i].to; if (v == fa) continue; for (int j = 0; j+val[v] <= K; ++j) dp[v][j+val[v]] = dp[u][j]; dfs(v, u); siz[u] += siz[v]; for (int j = 0; j <= K; ++j) dp[u][j] = (1ll*dp[u][j]*p[siz[v]-1]%mod+dp[v][j])%mod; } } ```