树形背包好题，推式子感觉十分自然，刚好用 LaTeX\LaTeX 推的式子顺便写一下题解。

Statement

给定一颗 nn 个节点的无向树，要求选取 kk 个特殊点，与这些特殊点相连的点（除自身外）被覆盖，求把 nn 个点全部覆盖的总方案数，答案对 109+710^9 + 7 取模（1≤n≤105,1≤k≤min⁡(n,100)1 \le n \le 10^5, 1 \le k \le \min(n, 100)）。

Solution

根据题意和数据范围不难想到是一个 O(nk)\mathcal{O}(nk) 的树形背包，因此我们直接上二维状态 dpver,kdp_{ver, k} 表示以 verver 为根的子树中选取 kk 个特殊点并且合法的总方案个数。

发现转移很难，因为不能表示所有的状态，父亲节点选取与否会影响它的子节点，考虑增加一维，定义 dpver,k,0/1dp_{ver, k, 0 / 1} 表示以 verver 为根的子树中选取 kk 个特殊点并且 verver 选取与否的总方案个数。

能转移么？发现还是很复杂，因为特殊点可以传递一层，不能知道一个不是特殊点的点是否被覆盖了，也就不能传递信息，考虑再大胆地增加一维记录当前点是否被覆盖，这样我们就得出来一个四维的 dpdp 状态：

钦定 dpver,k,0/1,0/1dp_{ver, k, 0 / 1, 0 / 1} 表示以 verver 为根的子树中，选取了一共 kk 个特殊点，并且 verver 节点上是否被选择了（0/10 / 1），verver 上是否被覆盖了（0/10 / 1）。

Transfer

根据树形背包的套路，假设当前在 verver 节点上，目标状态的特殊点个数为 sumsum，遍历完的子节点为 jj，并且 jj 的子树中选取了 partpart 个点，按照表达状态分为四种情况：

  1. dpver,sum,0,0dp_{ver, sum, 0, 0}：要求所有与其相连的所有儿子节点都不选择，但是由于其本身也不选，因此要保证子树中都被覆盖完全了，因为这是最后一次可以够得到 verver 的儿子节点，我们有：

    dpver,sum,0,0←dpj,part,0,1dp_{ver, sum, 0, 0} \gets dp_{j, part, 0, 1}

  2. dpver,sum,1,0dp_{ver, sum, 1, 0}：限制放宽了许多，但是仍然要求儿子节点不选择，但是儿子节点可以不被覆盖：

    dpver,sum,1,0←dpj,part,0,0+dpj,part,0,1dp_{ver, sum, 1, 0} \gets dp_{j, part, 0, 0} + dp_{j, part, 0, 1}

  3. dpver,sum,0,1dp_{ver, sum, 0, 1}：要求 verver 不被选又被儿子节点所覆盖，因此应当至少有一个儿子节点被选择，我们可以在子树的遍历时很好的处理：

    dpver,sum,0,1←dpj,part,1,1,dpj,part,0/1,1dp_{ver, sum, 0, 1} \gets dp_{j, part, 1, 1}, dp_{j, part, 0 / 1, 1}

  4. dpver,sum,1,1dp_{ver, sum, 1, 1}：要求 verver 被选择也被子树覆盖，因此条件和 33 情况类似，但是放宽了许多：

    dpver,sum,0,1←dpj,part,0/1,0/1dp_{ver, sum, 0, 1} \gets dp_{j, part, 0 / 1, 0 / 1}

上方大致叙述了转移的方向，但是我们仍要分情况讨论，采取经典的背包方式，可以得到最终的状态转移方程：

dpver,sum,0/1,0/1:={dpver,sum,0,0←∑j∈sonverdpver,sum−part,0,0×dpj,part,0,1,dpver,sum,1,0←∑j∈sonverdpver,sum−part,1,0×dpj,part,0,0/1,dpver,sum,0,1←∑j∈sonverdpver,sum−part,0,0×dpj,part,1,1+dpver,sum−part,0,1×dpj,part,0/1，1dpver,sum,1,1←∑j∈sonverdpver,sum−part,1,0×dpj,part1,0/1+dpver,sum−part,1,1×dpj,part,0/1,0/1dp_{ver, sum, 0 / 1, 0 / 1} := \left\{ \begin{array}{ll} \displaystyle dp_{ver, sum, 0, 0} \gets \sum_{j \in son_{ver}} dp_{ver, sum - part, 0, 0} \times dp_{j, part, 0, 1}, \\ \displaystyle dp_{ver, sum, 1, 0} \gets \sum_{j \in son_{ver}} dp_{ver, sum - part, 1, 0} \times dp_{j, part, 0, 0 / 1}, \\ \displaystyle dp_{ver, sum, 0, 1} \gets \sum_{j \in son_{ver}} dp_{ver, sum - part, 0, 0} \times dp_{j, part, 1, 1} + dp_{ver, sum - part, 0, 1} \times dp_{j, part, 0 / 1， 1} \\ \displaystyle dp_{ver, sum, 1, 1} \gets \sum_{j \in son_{ver}} dp_{ver, sum - part, 1, 0} \times dp_{j, part1, 0 / 1} + dp_{ver, sum - part, 1, 1} \times dp_{j, part, 0 / 1, 0 / 1} \end{array} \right.

对着这个方程写代码就能切了，注意状态转移时的上下界问题，要不然就变成 O(nk2)\mathcal{O}(nk ^ 2) 了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int ver, int pre)
{
    sz[ver] = 1;
    dp[ver][0][0][0] = dp[ver][1][1][0] = 1;
    for (int i = h[ver], to = e[i]; ~i; i = ne[i], to = e[i])
    {
        if (to == pre) continue;
        dfs(to, ver);
        sz[ver] += sz[to];

        memcpy(temp, dp[ver], sizeof temp), memset(dp[ver], 0, sizeof dp[ver]);
        for (int sum = min(k, sz[ver]); sum >= 0; sum --)
        // part + sz[ver] - sz[to] >= sum -> part >= sum - sz[ver] + sz[to]
            for (int part = min(sum, sz[to]); part >= max(0, sum - sz[ver] + sz[to]); part --)
            {
                dp[ver][sum][0][0] += temp[sum - part][0][0] * dp[to][part][0][1];
                dp[ver][sum][1][0] += temp[sum - part][1][0] * (dp[to][part][0][0] + dp[to][part][0][1]);
                dp[ver][sum][0][1] += temp[sum - part][0][0] * dp[to][part][1][1] + temp[sum - part][0][1] * (dp[to][part][0][1] + dp[to][part][1][1]);
                dp[ver][sum][1][1] += temp[sum - part][1][0] * (dp[to][part][1][0] + dp[to][part][1][1]) + temp[sum - part][1][1] * 
                    (dp[to][part][0][0] + dp[to][part][0][1] + dp[to][part][1][0] + dp[to][part][1][1]);
            }
    }
}