洛谷 P3177 [HAOI2015] 树上染色 - 对树形背包的思考

写写自己对书上背包的一些理解，聊的是洛谷 P3177 [HAOI2015] 树上染色，同步发在洛谷此题讨论区。

这里先贴一下原题吧：

---

[HAOI2015] 树上染色

题目描述

有一棵点数为 \(n\) 的树，树边有边权。给你一个在 \(0 \sim n\) 之内的正整数 \(k\) ，你要在这棵树中选择 \(k\) 个点，将其染成黑色，并将其他的 \(n-k\) 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

输入格式

第一行包含两个整数 \(n,k\)。

第二到 \(n\) 行每行三个正整数 \(u, v, w\)，表示该树中存在一条长度为 \(w\) 的边 \((u, v)\)。输入保证所有点之间是联通的。

输出格式

输出一个正整数，表示收益的最大值。

样例 #1

样例输入 #1

3 1
1 2 1
1 3 2

样例输出 #1

3

提示

对于 \(100\%\) 的数据，\(0 \leq n,k \leq 2000\)。

---

1. 前言

本文参考了 子谦。 的题解和 小心漂亮女人 的题解的思路，拜谢两位大佬orz。蒟蒻看了很久才看懂题解的底层逻辑，这篇堆了很多废话和简单逻辑（可能比较易懂？)，不过还是建议仔细读完这两篇题解再看这篇。

对于背包问题，被压掉的一维真是值得深思……

小心漂亮女人 的题解中的不合法情况去除问题原题解的说明加上例子已经讲得很清楚了，这里主要是想讲讲转移顺序问题 （两篇题解都着重强调我还是看了半天才看懂） 这个难点。

2. 分析

我们看到这里的双层循环（摘自 子谦。 的题解）：

for(int j=min(m,sz[u]);j>=0;--j){   //此处倒序枚举是为了避免重复选取
    if(f[u][j]!=-1)    //在DP前应先加上当前子节点的子树纯白色的情况，这是下面也倒序枚举的前提
        f[u][j]+=f[v][0]+(ll)sz[v]*(n-m-sz[v])*e[i].w;
    for(int k=min(j,sz[v]);k;--k){
        if(f[u][j-k]==-1)continue;
        ll val=(ll)(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;   //当前情况下连接子节点的边的贡献
        f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+val);
    }
}

先解释一下变量的含义：\(u\) 表示当前dfs处理的子树的根节点，\(v\) 表示 \(u\) 可到达的节点（除 \(u\) 的父节点）（\(v\) 也是 \(u\) 节点下的各子树的根节点），\(m\) 表示题目要求选的黑点数，\(sz[i]\) 表示以节点 \(i\) 为根的子树大小，\(k\) 表示 \(u\) 节点的子树上将要选择的黑点数。

实际上，前序后序遍历都不是重点（乱序都是可以的），但是 \(k=0\) 的情况却是十分特殊，这种情况和其他情况有本质上的差别。

首先，当我们更新 \(f[u][j]\) 时，我们自然想要使用前一个状态（即只合并过上一个和以前的子树的状态）来推出当前要合并的子树的状态。还记得 01 背包怎么压数组第一维吗？（从效果来看这里称作时间维度吧）当我们写出对容量 \(j\) 倒序遍历的时候，我们就已经用滚动数组的思想压掉了时间维度，因为当我们更新 \(f[u][j]\) 时，是用 \(f[u][j-k]\) 更新的，01 背包中的 \(k>0\)，则 \(j-k<j\) ，\(j\) 倒序遍历的时候 \(f[u][j-k]\) 就会在 \(f[u][j]\) 之后被更新，也就是说我们就是在用过去的状态更新现在的状态，自然就能滚动掉时间维度。

那么回到这里的树状背包，我们可以发现 \(k\) 的范围是 \([0,\min(j,sz[v])]\) ，是能取到 \(0\) 的，那么我们在更新 \(f[u][j]\) 时就会用到过去的状态 \(f[u][j-0]\)（跟现在 \(f[u][j]\) 一模一样！）更新现在（我更新我自己），为了让我们在更新现在的 \(f[u][j]\) 时用过去的 \(f[u][j-0]\) ，只需要在一开始的时候就先把 \(f[u][j]\) 自我更新，其实质上是在用过去的 \(f[u][j-0]\) 更新现在的 \(f[u][j]\) ，更新一结束 \(f[u][j]\) 就变成新的现在的状态了。

这种每次状态转移只需一次自我更新的尚且还可以把时间维度滚动掉，但如果每次状态转移需要更多这样的更新恐怕就不能滚动了……（可能是蒟蒻太菜，暂时想不到有什么办法）

不过如果之前没有更新过子树（f[u][j]==-1）就不需要先自我更新了~

至于剩余的状态嘛，就像 01 背包一样是还没被更新的数据（即目前还是过去的数据），完全可以任意序地更新 \(f[u][j]\) 。

那么正向从 \(0\) 开始遍历就是很自然地先作了它的自我更新，不需要特判 \(k=0\) 的情况 （懒癌晚期爱了），下面使用正向遍历的双层循环摘自 小心漂亮女人 的题解：

for(register int j = min(m, siz[x]); j >= 0; j--) // 最大取值为最多取的黑点的数量的子树大小的更小值， 再大的状态意义不合法 
{
    for(register int k = 0; k <= min(j, siz[y]); k++) // 同上，由于是要更新的状态的黑点数量为 j，所以在这个枚举中的上限要和 j 取更小值 
    {
        if(f[x][j - k] == -1) continue; // 特判掉不合法的情况 
        long long val = 1ll * e[i].w * k * (m - k) + 1ll * e[i].w * (siz[y] - k) * (n - m - siz[y] + k); // 这是新产生的贡献，由于很长的缘故，单独写出来 
        f[x][j] = max(f[x][j], f[x][j - k] + f[y][k] + val); // 看是否能够更新答案 
    }
}

3. 结语

其实无论是树形背包还是其他的背包，都需要注意被滚动掉的一维到底发生了什么，关注状态之间的依附关系，这一维关系到整个算法的正确与否。