树形背包的复杂度-CF1097G Vladislav and a Great Legend-解题报告

· · 题解

这道题还是比较简单比较套路的，用斯特林反演一下x^k，变成求组合数，变成对每个tuple求在多少点集中出现，树形DP即可。

具体的说，设dp[x][j]表示在x子树里选j条边的非空虚树方案数，在虚树点集的最浅点统计答案，合并子树时枚举选不选这条边。

其实我们对每种虚树算的方案数是这个东西：

2^{number~of~vertices~which~lie~on~some~path}\cdot\prod_{each~group}(2^{size~of~this~group}-1)

path是构成虚树的边，group是删除那些边后的剩下的子树们

你可能会好奇这个2的系数是什么时候出现的，我们在转移时并没有乘2这个操作啊。如果你手玩几个DP就会发现，这个2的系数在转移时以加法的形式出现。

然后就认为O(nk^2)过不去去看题解了。

然后发现每次循环\min(sz[v],K)就可以保证复杂度了。如果我说到这就停了，那和另一篇题解有什么区别

我们现在证明一下复杂度：

首先考虑合并两个子树A,B(Adfs序在前，B在后)的复杂度O(\min(sz[A],K)\times \min(sz[B],K))，可以理解为：从A的dfs序选出后K个，从B的dfs序选出前K个，然后它们两两配对起来的方案数。

这样，一个点x只会和dfs序相邻的左右2k个（一共4k）个点y匹配，因为再远了，要么x不是所在子树的dfs序后k个，要么y不是所在子树的dfs序前k个。

因此，总复杂度为O(nK)

void dfs(int x,int _fa)
{
    sz[x]=1,dp[x][0]=1;
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        dfs(v,x);
        static int f[N];
        for(ri i=0; i<=K; ++i) f[i]=dp[x][i];
        for(ri i=0; i<=K; ++i) inc(dp[x][i],dp[v][i]);
        for(ri i=1; i<=K; ++i) inc(dp[x][i],dp[v][i-1]);
        for(ri i=0; i<=sz[x]&&i<=K; ++i)
            for(ri j=0; j<=sz[v]&&i+j<=K; ++j)
            {
                int t=mul(f[i],dp[v][j]);
                inc(ans[i+j],t);
                inc(ans[i+j+1],t);
                inc(dp[x][i+j],t);
                inc(dp[x][i+j+1],t);
            }
        sz[x]+=sz[v];
    }
}