【树上背包】洛谷 P4516 [JSOI2018] 潜入行动

P4516 [JSOI2018] 潜入行动

省选/NOI-、树上背包计数

题意略

• 设状态为 \(dp[u][j][0/1][0/1]\) ，u 点子树放了 j 个装置，u 点有没有放装置，u 点有没有被监听的方案数。
• 对于转移时两点 u, v，考虑 u 点的情况
• 如果 u 没有放装置也没有被监听，v 一定不能放装置但 v 要被监听（否则 u 被监听）。

  • \[dp[u][i+j][0][0] = \sum dp[u][i][0][0] \times dp[v][j][0][1] \]

• 如果 u 没有放装置但被监听，v 的状态为被监听。对于 dp[u][k][0][1] 放不放装置无所谓， 对于 dp[u][k][0][0] v 必须放装置。

  • \[dp[u][i+j][0][1] = \sum dp[u][i][0][1] \times (dp[v][j][0][1] + dp[v][j][1][1]) + \sum dp[u][i][0][0] \times dp[v][j][1][1] \]

• 如果 u 放了装置但没有被监听，v 有没有被监听无所谓，一定没有放装置。

  • \[dp[u][i+j][1][0] = \sum dp[u][i][1][0]\times (dp[v][j][0][1] + dp[v][j][0][0]) \]

• 如果 u 放了装置且被监听，对于 dp[u][k][1][0]， v 一定放装置，有没有被监听无所谓。对于 dp[u][k][1][1] v 放不放装置，被不被监听都无所谓。

  • \[dp[u][i+j][1][0]=\sum dp[u][i][1][0]\times (dp[v][j][1][0] + dp[v][j][1][1]) \]

  • \[dp[u][i+j][1][1]=\sum dp[u][i][1][1]\times (dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]) \]

• 转移复杂度是 \(O(nk)\) ，数组不能开 long long ，转以后再更新子树大小。

const int N = 1e5 + 10, mod = 1e9 + 7;
int n, K;
vector<int> edge[N];
int dp[N][110][2][2], tmp[110][2][2], sz[N];

void dfs(int u, int p) {
    sz[u] = 1;
    dp[u][0][0][0] = dp[u][1][1][0] = 1;
    for (auto v: edge[u]) {
        if (v == p) continue;
        dfs(v, u);
        memcpy(tmp, dp[u], sizeof tmp);
        memset(dp[u], 0, sizeof tmp);
        for (int i = 0; i <= min(sz[u], K); i++) {
            for (int j = 0; j <= min(sz[v], K) && i + j <= K; j++) {
                dp[u][i + j][0][0] += 1ll * tmp[i][0][0] * dp[v][j][0][1] % mod;
                dp[u][i + j][0][1] += (1ll * tmp[i][0][1] * (dp[v][j][0][1] + dp[v][j][1][1]) + 1ll * tmp[i][0][0] * dp[v][j][1][1]) % mod; 
                dp[u][i + j][1][0] += 1ll * tmp[i][1][0] * (dp[v][j][0][1] + dp[v][j][0][0]) % mod;
                dp[u][i + j][1][1] += (1ll * tmp[i][1][0] * (dp[v][j][1][0] + dp[v][j][1][1]) +
                    1ll * tmp[i][1][1] * (1ll * dp[v][j][0][0] + dp[v][j][0][1] + dp[v][j][1][0] + dp[v][j][1][1])) % mod;
                if (dp[u][i + j][0][0] >= mod) dp[u][i + j][0][0] -= mod;
                if (dp[u][i + j][0][1] >= mod) dp[u][i + j][0][1] -= mod;
                if (dp[u][i + j][1][0] >= mod) dp[u][i + j][1][0] -= mod;
                if (dp[u][i + j][1][1] >= mod) dp[u][i + j][1][1] -= mod;
            }
        }
        sz[u] += sz[v];     // 转移后再更新子树大小
    }
    return ;
}

int main() {
    re(n), re(K);
    for (int i = 1; i < n; i++) {
        int a, b;
        re(a), re(b);
        edge[a].pb(b), edge[b].pb(a);
    }
    dfs(1, -1);
    ll ans = (dp[1][K][0][1] + dp[1][K][1][1]) % mod;
    printf("%lld\n", ans);
    return 0;
}