对一些很难理解的点的思考

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

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

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

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

CPP

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-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

的情况 ~~（懒癌晚期爱了）~~，下面使用正向遍历的双层循环摘自小心漂亮女人的题解：

CPP

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); // 看是否能够更新答案 
	}
}

还有什么疑惑欢迎下面讨论或者私信~

对一些很难理解的点的思考

讨论操作

回复

相关推荐

对一些很难理解的点的思考