一道毒瘤树型DP,主要是因为要用高精.

首先定义状态 fi,jf_{i,j} 表示以 ii 为根的子树,连通块大小为 jj,那么这个状态记录的是什么? 它表示除去 ii 所在的连通块的贡献答案的最大值,只需要在最后统计答案的时候再加回去.

那么可以得到状态转移方程

fu,j=max⁡v∈u,1≤k≤j1≤j≤size(u)(fu,k+fv,j−k)f_{u,j}=\max_{v \in u,1 \le k \le j}^{1\le j\le size(u)}(f_{u,k}+f_{v,j-k})

fu,0=max⁡1≤j≤size(u)fu,j×jf_{u,0}=\max_{1 \le j \le size(u)}f_{u,j}\times j

然后再加上一个高精就行了

部分代码

void dfs(int u, int fa)
{
    siz[u] = 1, f[u][0] = f[u][1] = 1;
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (v == fa)
            continue;
        dfs(v, u);
        siz[u] += siz[v];
        for (int j = siz[u]; j >= 1; j--)
            for (int k = min(siz[u] - siz[v], j); k >= max(1, j - siz[v]); k--)//注意枚举顺序
                f[u][j] = max(f[u][j], f[u][k] * f[v][j - k]);                
    }
    for (int i = 0; i <= siz[u]; i++)
        f[u][0] = max(f[u][i] * i, f[u][0]);
}