树形背包导论

almost copied from 英才计划论文.

定义

一般来说，树形背包的问题可以抽象为如下形式：

给定 $n$ 个物品，物品间的选择存在依赖关系，以依赖关系的边可以构成一棵树。

现在请你选择 $k$ 个物品使得选择价值最大。

我们先定义状态 $f_{x,i}$ 表示点 $x$ 体积为 $i$ 的状态。

这个问题本质上等价于一个分组背包模型，即儿子集合内每个状态 $f_{y,j}$ 可以被视为一个体积为 $j$，价值为 $f_{y,j}$ 的物品，而每个子树设为一个组，那么转移方程显然就是：
$$
f_{x,k} = \max\limits_{\sum\limits_{i = 1}^p c = t-1} \sum\limits_{i=1}^p f_{y,c} + val(x)
$$
暴力转移，我们容易得到复杂度是 $\mathcal{O}(nk^2)$的。

优化

我们考虑转移复杂度劣的原因，实际上会使得每个节点都会在父节点处被处理，所以相当于每个父节点处都会计算子树内所有节点的值。故上述方程容易被特殊构造的链状数据卡到最差 $O(n^3)$ 的复杂度。

所以我们需要控制枚举的上界，具体来说，不妨假设存在全选子树内的节点的情况，那么在过程中完成 $y(y \in s(x))$ 到 $x$ 的转移后，$x$ 的枚举上界应为 $|s(x)| + |\text{subtree}(y)|$ ，此处 $\text{subtree}(y)$ 表示以 $y$ 为根的子树。$y$ 的枚举上界应为 $\min{|\text{subtree}(y)|,chos-1}$，其中 $chos$ 是上文提到的枚举 $x$ 的子树内选择个数。

上文的实现方式实际上还是会存在枚举到不合法的情况，故我们需要进行一个类似卷积的过程。对于一个节点 $x$ 和 $y(y \in s(x))$，在过程中枚举 $x$ 的选择点数 $i$ 和 $y$ 的选择点数 $j$，并且用一个临时数组存储下 $f_{x,i}$ 和 $f_{y,j}$ 的和，每次用 $f_{x,i}$ 和 $f_{y,j}$ 来更新 $i+j$ 并且取最小值。

此处给出伪代码实现参考：

//In C++
//subtree[x] 代表上文提到的子树大小
//f[x][k] 表示上文提到的状态转移
for (int i = subtree[x];i >= 0;--i) {
	for (int j = subtree[y];j >= 0;--j) {
		tmp[i+j] = max(tmp[i+j],f[x][i] + f[y][j]);
    }
}
for (int i = subtree[x];i >= 0;--i) {
	f[x][i] = tmp[i];
}
subtree[x] += subtree[y];

上文提到的转移方法的时间复杂度是 $\Theta(nk)$ 的，此处给出证明。

(参考：cervoliu-子树合并背包类型的dp的复杂度证明 https://blog.csdn.net/lyd_7_29/article/details/79854245)

定义大小超过 $k$ 的子树为大子树，反之为小子树。

一个极小的大子树一定是由若干个极大的小子树合并而成的，而且合并的过程中就会从极大的小子树变成极小的大子树。

假设所有的极大的小子树的大小分别为$x_1,x_2,x_3,\dots.x_m$，显然 $x_1+x_2+…+x_m\leq n $，将这些小子树并入大子树的复杂度为 $k\times (x_1+x_2+…+x_m)\leq n_k$，可以认为是每个极大的小子树被消灭掉所产生的总时间代价不超过 $nk$。

考虑一个极大的小子树（大小 $x\leq k$）内部合并上来的复杂度，由上面的分析知是$ x^2$ 的。
因此每个小子树内部合并的复杂度就是$x_1^2+x_2^2+\dots +x_m^2,xi\leq k$，显然当尽量多的 $x_i$ 取到 $k$ 这个值才会更大，因为假设$\sum\limits_{1\leq i\leq n} x_i = n$为定值，$x_1>x_2$，如果让$x_1+1,x_2–1$，上面那个值会变大。这样复杂度就是$\Theta(\frac{n}{k} \times k^2) = \Theta(nk)$

最后，考虑将所有的极小大子树合并成整棵树的复杂度，显然极小的大子树互不包含，因此极小的大子树个数不会超过 $\frac{n}{k}$ 个，而每合并两个的时间开销是 $k^2$ ，因此这部分复杂度是 $\Theta(\frac{n}{k} \times k^2) = \Theta(nk)$

例题

Luogu P3177 HAOI2015 树上染色

有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他 的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

$n,k \leq 2000$

我们考虑从边的角度来思考，那么原题所求的就变成了求每条边被一对黑点或一对白点经过几次。考虑把边左右端点分成两棵树，那么答案就是左边黑点数 * 右边黑点数 + 左边白点数 * 右边白点数。

接下来考虑，每个点被决策成为黑点/白点对答案造成的影响。我们设左边子树的黑点有 $m$ 个，则易得右边子树的黑点有 $k-m$ 个，那么容易计算：
$$
ans = m \times (k-m)+(siz_l-k)\times(n - k - (siz_l - k))
$$
那么我们考虑，我们把这个过程放到树上来考虑。我们依然设计经典的 $f_{x,i}$ 表示点 $x$ 子树内有 $i$ 个黑点，转移的时候我们只需要讨论 $(x,y)$ 这条边的贡献就可以了。也就是转移：
$$
f_{x,i} = \max\limits_{j = 0}^i{f_{x,i-j} + f_{y,j} + ans * w_{(x,y)}}
$$
利用上方转移，我们可以做到时间复杂度 $\mathcal{O}(n^2)$。

const int N = 2010; 
const int M = N<<1;
int hd[N],edg[M],nxt[M],to[M],tot;
int siz[N],n,m;
ll f[N][N];

inline void add(int u,int v,int w) {
	edg[++tot] = w;to[tot] = v;nxt[tot] = hd[u];hd[u] = tot;
}

inline void addedge(int u,int v,int w) {
	add(u,v,w);add(v,u,w);
}

void dfs(int x,int fa) {
	siz[x] = 1;f[x][0] = f[x][1] = 0;
	for (int i = hd[x];i;i = nxt[i]) {
		int y = to[i];
		if (fa == y) continue;
		dfs(y,x);
		siz[x] += siz[y];
		for (int j = min(siz[x],m);j >= 0;--j) {
			if (f[x][j] != -1) {
				f[x][j] += f[y][0] + (ll)siz[y] * (n-m-siz[y]) * edg[i];
			}
			for (int k = min(siz[y],j);k > 0;--k) {
				if (f[x][j-k] == -1) continue;
				ll tmp = (m-k)*k+((n-m)-(siz[y]-k))*(siz[y]-k);
				f[x][j] = max(f[x][j],f[x][j-k] + f[y][k] + tmp * edg[i]);
			}
		}
	}
}

int main() {
	read(n,m);
	if(n-m<m)m=n-m;
	for (int i = 1;i < n;++i) {
		int x,y,z;
		read(x,y,z);
		addedge(x,y,z);
	}
	memset(f,-1,sizeof(f));
	dfs(1,0);
	printf("%lld",f[1][m]);
	return 0;
}

一道题

一棵 $n$ 个点的树（$n$ 为偶数），将树上的点两两匹配。也就是说对于任意一个结点 $u$，有且仅有一个结点 $v$ 与之配对。

对于匹配有一些限制。对于两个匹配 $(u,v)$ 和 $(x,y)$，婷姐要求这两个匹配要么相离，要么一个包含另一个。

• 相离：$u$ 到 $v$ 的路径与 $x$ 到 $y$ 的路径不相交。
• 包含：$u$ 到 $v$ 的路径包含 $x$ 到 $y$ 的路径或者 $x$ 到 $y$ 的路径包含 $u$ 到 $v$ 的路径。

婷姐需要你告诉他，这样的匹配一共有多少种方案。答案对 $998244353$ 取模。

两个方案不同当且仅当存在某个结点，使得在这两个方案中与它配对的那个结点不同。

$n \leq 2000$

这道题乍看很难联系到树形背包上，所以我们先设计一个暴力的状态 $f_{x,i}$ 表示我们考虑从 $x$ 出发的一条长度为 $i$ 的链。

我们考虑怎样刻画一个匹配，可以发现，我们考虑一条链 $(u,v)$，实际上可以从他们的一个“中转点” $x$ 来考虑。假设 $len_{(u,x)} = i,len_{(x,v)} = j$，那么我们就有
$$
f_{x,i + j+1} = val_{(u,v)}\times (f_{u,i} + f_{v,j})
$$
可以发现，这个本质上是一个只考虑两个子树的背包合并！