树形背包的较严谨复杂度证明

发表于 更新于 分类于

树形背包的比较严谨的复杂度证明

转移方式

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int u,int fa=0){
	sz[u]=1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);sz[u]+=sz[v];
		for(i=min(k,sz[u]);i>=0;i--){
			for(j=max(0,i-(sz[u]-sz[v]));j<=i&&j<=sz[v];j++){
                //O(trans) do something
			}
		}
	}
}

证明，总复杂度为 \(O(n^2)\)

证明 \(n^2\) 直接忽略 \(i\) 的循环和 \(k\) 取 \(\min\) 的操作。

考虑在某个点合并子树的过程，本质上，如果把 \(sz_u\) 看成当前子树内所有的点，我们的第一个循环是限制了合并后的总大小，第二个循环限制了已经合并的子树的大小，以及待合并的子树的大小。

所以在一个点 \(u\) 处，只有每一对以它为 LCA 的点对会贡献一次，其它点对均不贡献。

所以总复杂度为点对数量 \(O(n^2)\)

证明，总复杂度为 \(O(trans\times min(n^2,nk))\)

\(O(n^2)\) 的证明是老生常谈的事情了，考虑 \(k\leq n\) 的情况，试证明总复杂度为 \(O(nk)\)

考虑一对点在 LCA 处的贡献，

考虑合并子树时的三种 case，小于 \(k\) 向大于 \(k\) 合并，大于 \(k\) 向大于 \(k\) 合并，小于 \(k\) 向小于 \(k\) 合并。

我们分别说明三种情况的时间复杂度都是 \(O(nk)\) 的。

Case1

小于合并到大于。

准确的说，是小于 \(k\) 的子树合并之后，大小大于 \(k\)

考虑每一个点对这种情况的贡献，每个点显然只会参与一次过程，因为参与之后它所在的块的大小就大于 \(k\) 了。

总复杂度 \(O(nk)\)

Case2

大于合并到大于。

考虑每一次合并，复杂度 \(O(k^2)\)，会永远失去一个大于 \(k\) 的块。而我们最多会生成 \(\frac{n}{k}\) 个大小大于 \(k\) 的块，因为一个点至多参与一次生成新块的过程。

总复杂度 \(O(nk)\)。

Case3

小于合并到小于，那么这种情况就只会发生于大小小于 \(k\) 的子树内以及其父亲的子树间。如果一个点的父亲的大小也不超过 \(k\)，我们忽略它本身，直接在它的父亲处计算所有复杂度贡献。这样所有的复杂度分成两个部分，小于 \(k\) 的子树内，以及其兄弟间（也就是在一棵很大的子树中，有几个比较小的儿子先合并了）。

第一部分的复杂度显然是 \(\leq nk\) 的（本质上是选了几个自身不超过 \(k\)，和不超过 \(n\) 的变量求平方和，参考 \(n^2\) 的证明）

第二部分，每个点只会参与一次这个过程，因为参与一次之后它所在的块大小就大于 \(k\) 了，所以这一部分的总复杂度也是 \(O(nk)\) 的

综上所述，树形背包的复杂度为 \(O(nk)\)。

思考

在上面的代码的边界做一些改动，哪些改动会让复杂度假掉。