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

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

转移方式

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)$。

思考

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