题意

给定一棵树，删除若干条边，求连通块大小之积的最大值是什么

题解

实际上这题有两种做法。一个是贪心，一个是动规，但是我只会DP做法。

设状态为 $dp[u][j]$ 表示与 $u$ 相连的连通块大小为 $j$ 的答案（这里的连通块大小是包裹 $u$ 本身的）。

然后整个子树的答案我们存在 $dp[u][0]$ 里，因为我们发现这个状态实际上是没有实际含义的。

接下来考虑转移，我们枚举一个合并好的前缀，然后往两边分配大小。另外这里合并两个答案的大小统计要留到最后，这是为了防止状态的混淆。

细节看代码。

另外有一个超级大坑，就是转移的顺序，一定要从大的往小的转移，因为要防止数据被覆盖qwq。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dfs(int u, int fa) {
    sz[u] = 1; dp[u][1] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa) continue;
        Dfs(v, u);
        for(int j = sz[u] + sz[v]; j >= 1; j--) {
            for(int k = 0; k <= sz[v]; k++) {
                int l = j - k;
                if(l < 1 || l > sz[u]) continue;
                dp[u][j] = max(dp[u][j], dp[u][l] * dp[v][k]);
            }
        }
        sz[u] += sz[v];
    }
    for(int i = 1; i <= sz[u]; i++) {
        dp[u][0] = max(dp[u][0], dp[u][i] * i);
    }
}