树形背包好题,推式子感觉十分自然,刚好用 LATEX 推的式子顺便写一下题解。
Statement
给定一颗 n 个节点的无向树,要求选取 k 个特殊点,与这些特殊点相连的点(除自身外)被覆盖,求把 n 个点全部覆盖的总方案数,答案对 109+7 取模(1≤n≤105,1≤k≤min(n,100))。
Solution
根据题意和数据范围不难想到是一个 O(nk) 的树形背包,因此我们直接上二维状态 dpver,k 表示以 ver 为根的子树中选取 k 个特殊点并且合法的总方案个数。
发现转移很难,因为不能表示所有的状态,父亲节点选取与否会影响它的子节点,考虑增加一维,定义 dpver,k,0/1 表示以 ver 为根的子树中选取 k 个特殊点并且 ver 选取与否的总方案个数。
能转移么?发现还是很复杂,因为特殊点可以传递一层,不能知道一个不是特殊点的点是否被覆盖了,也就不能传递信息,考虑再大胆地增加一维记录当前点是否被覆盖,这样我们就得出来一个四维的 dp 状态:
钦定 dpver,k,0/1,0/1 表示以 ver 为根的子树中,选取了一共 k 个特殊点,并且 ver 节点上是否被选择了(0/1),ver 上是否被覆盖了(0/1)。
Transfer
根据树形背包的套路,假设当前在 ver 节点上,目标状态的特殊点个数为 sum,遍历完的子节点为 j,并且 j 的子树中选取了 part 个点,按照表达状态分为四种情况:
-
dpver,sum,0,0:要求所有与其相连的所有儿子节点都不选择,但是由于其本身也不选,因此要保证子树中都被覆盖完全了,因为这是最后一次可以够得到 ver 的儿子节点,我们有:
dpver,sum,0,0←dpj,part,0,1
-
dpver,sum,1,0:限制放宽了许多,但是仍然要求儿子节点不选择,但是儿子节点可以不被覆盖:
dpver,sum,1,0←dpj,part,0,0+dpj,part,0,1
-
dpver,sum,0,1:要求 ver 不被选又被儿子节点所覆盖,因此应当至少有一个儿子节点被选择,我们可以在子树的遍历时很好的处理:
dpver,sum,0,1←dpj,part,1,1,dpj,part,0/1,1
-
dpver,sum,1,1:要求 ver 被选择也被子树覆盖,因此条件和 3 情况类似,但是放宽了许多:
dpver,sum,0,1←dpj,part,0/1,0/1
上方大致叙述了转移的方向,但是我们仍要分情况讨论,采取经典的背包方式,可以得到最终的状态转移方程:
dpver,sum,0/1,0/1:=⎩⎨⎧dpver,sum,0,0←j∈sonver∑dpver,sum−part,0,0×dpj,part,0,1,dpver,sum,1,0←j∈sonver∑dpver,sum−part,1,0×dpj,part,0,0/1,dpver,sum,0,1←j∈sonver∑dpver,sum−part,0,0×dpj,part,1,1+dpver,sum−part,0,1×dpj,part,0/1,1dpver,sum,1,1←j∈sonver∑dpver,sum−part,1,0×dpj,part1,0/1+dpver,sum−part,1,1×dpj,part,0/1,0/1
对着这个方程写代码就能切了,注意状态转移时的上下界问题,要不然就变成 O(nk2) 了。
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 --) 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]); } } }
|