题目链接

P8352 [SDOI/SXOI2022] 小 N 的独立集

解题思路 & 参考代码

$O(n^3k^4)$：

考虑 dp，设 $f_{u,x,y}$ 表示以 $u$ 为根的子树，选 / 不选 点 $u$ 时最大权独立集大小分别为 $x,y$ 时的方案数。

容易转移：

$$f_{u,x_1+y_2,y_1 + \max(x_2,y_2)} \gets f_{u,x_1,y_1} \times f_{v,x_2,y_2}$$

那么就做完了，时间复杂度 $O(n^3k^4)$，不能通过本题。

$O(n^2k^4)$：

考虑优化 $O(n^3k^4)$ 的做法。

注意到当 $x \le y$ 时记录 $x$ 是没有意义的，而 $x>y$ 时一定有 $x - y \le k$。

因此我们可以修改以下状态，设 $f_{u,i,y}$ 表示以 $u$ 为根的子树，选 / 不选 点 $u$ 时最大权独立集大小分别为 $y+i,y$ 时的方案数（特别的，若 $i = 0$，则代表此时 $x \le y$）。

同样容易转移：

$$f_{u,\max(i_1-i_2,0),y_1+y_2+i_2} \gets f_{u,i_1,y_1} \times f_{v,i_2,y_2}$$

时间复杂度 $O(n^2k^4)$，可以通过此题。

:::info[参考代码]

ll n,m;
ll x,y;
vector<ll>G[1010];
ll f[1010][6][5010];
ll g[6][5010];
ll sz[1010];
void Dfs(ll x,ll fa)
{
    sz[x]=1;
    forl(i,1,m)
        f[x][i][0]=1;
    for(auto i:G[x])
        if(i!=fa)
        {
            Dfs(i,x);
            forl(j,0,m)
                forl(k,0,(sz[x]+sz[i])*m)
                    g[j][k]=0;
            forl(i1,0,m)            
                forl(y1,0,sz[x]*m)
                    if(f[x][i1][y1])
                        forl(i2,0,m)
                            forl(y2,0,sz[i]*m)
                                add(g[max(i1-i2,0ll)][y1+y2+i2],f[x][i1][y1]*f[i][i2][y2]);
            sz[x]+=sz[i];
            forl(j,0,m)
                forl(k,0,sz[x]*m)
                    f[x][j][k]=g[j][k];
        }
}
void solve()
{
    cin>>n>>m;
    forl(i,2,n)
        cin>>x>>y,
        G[x].pb(y),
        G[y].pb(x);
    Dfs(1,0);
    forl(i,1,n*m)
    {
        ll S=0;
        forl(j,0,min(i,m))
            add(S,f[1][j][i-j]);
        cout<<S<<endl;
    }
}

:::