This is not the end.

0%

一种树形背包的复杂度证明

Posted on

有一类树上背包（例如 CF1097G Vladislav and a Great Legend），第二维表示子树内选的点数且限制第二维不超过$m$，其总复杂度可证明为$O(nm)$。

它们的代码一般长这样：

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int u,int last) {
	sz[u]=1;
	// initialize dp[u]
	for(int k=head[u];k;k=e[k].next)
	{
		int v=e[k].to; if(v==last) continue;
		dfs(v,u);
		for(int j=0;j<=min(m,sz[u]);++j)
			for(int k=0;k<=min(m-j,sz[v]);++k)
				// dp[u][j] * dp[v][k] -> dp[u][j+k]
	}
}

为了避免混淆，用$sz$表示已经每个点已经合并上来过的点数，$size$表示每个点的子树大小。

主要的时间开销是在合并$u$和$v$两个点的背包上。分四种情况来讨论：

  • $sz[u] \ge m, size[v] \ge m$
    一次合并的复杂度为$O(m^2)$。考虑所有的极小的$size \ge m$的子树（即它里面的所有子树的$size$都小于$m$），显然它们两两不相交，所以至多有$\frac{n}{m}$个。此外，这种情况会出现，当且仅当：$u$已经合并过的儿子里有极小的子树，并且$v$里面有极小的子树。故而合并的次数为极小的子树个数 - 1。故而这一部分的复杂度是$O(m^2 \cdot \frac{n}{m}) = O(nm)$
  • $sz[u] \ge m, size[v] < m$
    这种情况的复杂度是$O(m\cdot size[v])$，我们考虑求$\sum size[v]$的上界。对于每一个点考虑，它的祖先中，满足$size[x] < m \wedge size[fa_x] \ge m$的点至多只有一个，所以会出现这种情况的$(u,v)$至多只有一个，所以$\sum size[v] = O(n)$，所以这种情况的总复杂度是$O(nm)$。
  • $sz[u] < m, size[v] \ge m$
    类似地我们考虑求$\sum sz[u]$的上界。对于$sz[u]$中的每个点考虑，它的祖先中出现这种情况的$u$也至多有一个、并且每个$u$只会出现至多一次这种情况，所以$\sum sz[u] = O(n)$。
  • $sz[u] < m, size[v] < m$
    这个时候就是普通的树形背包，对于一整棵大小为$x$的树我们知道这样的复杂度是$O(x^2)$。考虑所有的、极大的$size < m$的子树（即满足$size[fa_x] \ge m$），每一个这样的子树的复杂度是$O(m^2)$，而这样的子树两两不相交，所以至多有$n\over m$个，所以总复杂度为$O(m^2 \cdot \frac{n}{m})$。

综上所述，时间复杂度为$O(nm)$。