回溯形树状 DP

这篇文章内容不难，但可以帮助我们重新整理对回溯形树状 DP 的思路。

什么叫「回溯形树状 DP」？我们来看一道例题：

Apple Tree ——POJ 2486

有一颗苹果树，每个节点上面有不同数量的苹果，从一个节点到另外一个可以到达的节点花费 \(1\) 步，求 \(s\) 步最多能吃到多少苹果。起始点为 \(1\)，可以不回到起始点。

我们会自然地想到：设置 \(dp_{i,j}\) 数组，表示在以 \(i\) 为根的子树（以后用 \(G_i\) 表示）中，从 \(i\) 出发，行走 \(j\) 步，吃到的最多苹果数。不过，仔细思考可以发现，考虑节点 \(i\)，在进入到它的子树后是否返回子树的根节点，对统计结果是会有影响的。于是，我们可以考虑多加一维，表示向下行走后是否返回当前结点。

这样，我们重新定义数组 \(dp_{i,j,0/1}\)，表示 \(G_i\) 中，从根节点开始行走 \(j\) 步，吃到的最多苹果数，其中，\(0\) 表示不需回到根节点，\(1\) 表示需要回到根节点。我们最终需要得到 \(max(dp_{1,s,0},dp_{1,s,1})\)。

在这篇文章里，我们把像这样在树形 DP 过程中需要考虑是否返回的问题叫做「回溯形树状 DP」。

现在我们考虑：如何求 \(dp\) 数组的递推式？我们先给出答案：

对于 \(G_{root}\)，我们有：

\[\begin{align} dp_{root,j,0}=max\{dp_{root,j-k,1}+dp_{son,k-1,0}\}\\dp_{root,j,0}=max\{dp_{root,j-k,0}+dp_{son,k-2,1}\}\\dp_{root,j,1}=max\{dp_{root,j-k,1}+dp_{son,k-2,1}\}\\ \end{align}\]

其中，\(son\) 为 \(root\) 的子节点，\(k\) 表示额外分给 \(son\) 的步数。对于第一行，\(1 \leq k \leq j\)；对于后两行，\(2 \leq k \leq j\)。

很明显，在实际操作中，若要得到 \(dp_{root,j,0/1}\)，我们需要枚举 \(son\) 和 \(k\)。接下来我们详细地分析一下这个方程。

我们倒着来，先看第三行。它表示的是要求返回根结点时的情况。我们已经把 \(k\) 步分配给了 \(son\)，那么剩下的子树还剩 \((j-k)\) 步，并且要返回到根节点；再看 \(son\)，由于我们要花一步到达 \(son\)，再花一步从 \(son\) 返回 \(root\)，所以实际上 \(G_{son}\) 只会得到 \((k-2)\) 步。这就是 \(dp_{root,j-k,1}+dp_{son,k-2,1}\) 的来历。对所有结果取最大值，我们就得到了第三行方程。

然后看前两行，它们代表不需返回根节点的情况。类似地分析，可以发现：

• 第一行表示先进入其它子树中并返回，然后 \(G_{son}\) 中，不再返回。这时 \(G_{son}\) 实际分得的步数为 \(k-1\)。
• 第二行表示先进入 \(G_{son}\) 中并返回，然后进入其它子树中，不再返回。这时 \(G_{son}\) 分得的步数为 \(k-2\)。

这都是与上述方程相符的。至此，整个 \(dp\) 数组就被我们分析完了。不过，还有一些疑点：为什么上面的 \(dp_{root,j-k,0/1}\) 就表示除 \(G_{son}\) 之外的其它子树？另外，边界是什么？该按照什么顺序求解这个数组？

我们需要理解这道题的具体实现。树形 DP 常常使用 DFS 求解，下面，我们看看这道题的 dfs 函数：

void dfs(int root, int father) {  
  for (int i = head[root]; i != -1; i = edge[i].next) {  
    int son = edge[i].v;  
    if (son == father) continue;  
    dfs(son, root);
    for (int j = s; j >= 1; j--) {
      for (int k = 1; k <= j; k++) {  
        dp[root][j][0] = max(dp[root][j][0], dp[root][j-k][1] + dp[son][k-1][0]); 
        if (k > 1) { 
          dp[root][j][0] = max(dp[root][j][0], dp[root][j-k][0] + dp[son][k-2][1]);  
          dp[root][j][1] = max(dp[root][j][1], dp[root][j-k][1] + dp[son][k-2][1]); 
        }
      }  
    }  
  }  
}

这一块代码似乎很难理解消化。为了便于解释，我们把上面的代码去粗取精：

dfs(root) {  
  for each son of root {  
    dfs(son);
    for (int j = s; j >= 1; j--)
      for (int k = 2; k <= j; k++)
        dp[root][j][1] = max(dp[root][j][1], dp[root][j-k][1] + dp[son][k-2][1]);
  }
}

现在我们针对下面的子树，一步一步分析。

我们从 \(son_1\) 开始枚举。首先我们对 \(son_1\) 执行 DFS 操作，这就得到了所有和 \(son_1\) 有关的信息。

然后，我们枚举 \(j\)，即 \(G_{root}\) 所分得的步数。（不难发现这是有用的，因为我们待会儿要用到 \(son_1\) 的这些信息。）

接着对于每个 \(j\) 枚举 \(k\)，即分给子树的步数，并根据方程式 \(dp_{root,j,1}=max\{dp_{root,j-k,1}+dp_{son,k-2,1}\}\) 进行计算。不过等等，枚举 \(j\) 的时候是递减的，\(j-k<j\)，这时的 \(dp_{root,j-k,1}\) 不是还为 \(0\) 么？

不要着急，我们接着往下看。当我们枚举到 \(son_2\) 时，还会再算一次 \(dp_{root,j,1}\)。这时的 \(dp_{root,j-k,1}\) 就不为 \(0\) 了，因为在枚举 \(son_1\)，步数为 \(j-k\) 时，我们已经给 \(dp_{root,j-k,1}\) 赋了一个值。当然，这个值只包含了 \(G_{son_1}\) 的贡献。那么，这时就会有：

\[dp_{root,j-k,1}+dp_{son_2,k-2,1}=dp_{son_1,j-k-2,1}+dp_{son_2,k-2,1}\]

即为进入 \(son_1\) 后返回，再进入 \(son_2\) 后返回，共花 \(j\) 步，吃到的最多苹果数。但别忘了，我们要枚举分给子树的步数，并把结果与当前的 \(dp_{root,j,1}\) 求最大值。因此，在枚举过 \(son_2\) 后，\(dp_{root,j,1}\) 就会出现两种情况：

1. 如果能找到更大的答案，则存储的就是进入 \(son_1\) 再进入 \(son_2\) 的最多苹果数。
2. 如果没有更大的答案，则存储的就是只进入 \(son_1\) 得到的最多苹果数。

还有一种可能，就是只进入 \(son_2\)。这个算法包含了这种可能么？包含了。当我们把 \(j\) 步全部分给 \(son_2\) 时，就是只进入 \(son_2\) 的情况。它包含在情况 1 中。

综上，所有的情况都考虑到了。因此，至少当枚举完 \(son_2\) 时，这个算法是没有问题的。那么，以后的操作就十分类似了：当枚举 \(son_3\) 时，\(dp_{son_1,j-k,1}\) 仅包括 \(son_1\) 和 \(son_2\) 的贡献。然后，通过枚举给 \(G_{son_3}\) 的步数，我们找到了此时 \(dp_{root,j,1}\) 的最优值。以此类推，当枚举完所有子树时，我们就得到了把 \(j\) 步分给下面的子树，能摘到的最多苹果数。

回头想想，这个问题很像 01 背包——从这行代码就能看出来：

for (int j = s; j >= 1; j--)

实际上，这里确实有 01 背包的思想： j-- 保证了数组中当前位置前的数还是上一步的状态，而我们需要它们来推出这一步的状态。在上面的代码中，这种实现方式是极为重要的。

至于初值，我们可以给 \(dp\) 数组中的每个值赋为其描述的子树的根节点上的苹果数——无论如何这都是最少能摘到的苹果数，而它作为边界条件也是有效的。

实际上，这个 j-- 的代码不仅适合于回溯形树状 DP，还适合于所有将某样东西分给子节点，求最优方案的问题——不仅仅是步数。