关于树上背包

本人下午在做P1273 有线电视网一题时偶然看到讨论区里的HACK，然后使用我的该题的 AC 代码并不能通过这个讨论区中的 HACK，经我检验后发现是我的代码的时间复杂度是假的，实际上应该是

O(n^3)

，原因我大概已经理解了，但是为什么几乎全网所有的树上背包板子都采用这种写法，且几乎所有的人都说这样写的时间复杂度上界是 $O(n^2)$ 的。

我的代码中的核心部分是：

CPP

	for(ll i=0;i<lz;i++){
		dfs(e[u][i]);
		siz[u]+=siz[e[u][i]];
		for(ll j=siz[u];j;j--){
			for(ll k=0;k<=min(j,siz[e[u][i]]);k++){
				f[u][j]=min(f[u][j],f[u][j-k]+f[e[u][i]][k]+quan[u][i]);
			}
 		}
	}

简单论证一下这份代码的时间复杂度不是

O(n^2)

的：

简单地说就是证明时间复杂度的人会把上述操作视为合并大小为 $a,b$ 的子树，并把时间复杂度视为 $O(ab)$ ，但实际上是不对的，因为代码中在转移之前进行了 siz[u]+=siz[e[u][i]] 的操作，所以说进行的转移实际上是 $O(ab+b^2)$ 的，而这就导致不能把时间复杂度简单看成树上枚举两点了，上界的 $O(n^3)$ 是显然的。

现在我已知的时间复杂度上界为

O(n^2)

的方法有且仅有一个：

基于 dfs 序转化的第一篇题解

我认为大概应该存在除了 dfs 序之外的严格 $O(n^2)$ 的做法，但是自行 bdfs 后无果，基本上时间复杂度都是假的，遂来求助无所不能的谷民，希望能够得到代码以及附加的时间复杂度分析，万分感谢！！！

讨论操作

回复

相关推荐

关于树上背包