首先，我们发现，转移一颗子树的背包，实际上就是把该子树的根节点的所有儿子的子树背包合并，再与根节点合并。具体的，合并两颗子树的转移方程式如下：
于是有如下伪代码：
dfs(u) :
su = 1
f(u, 1) = w[u]
for (v in u)
sv = size(v)
for (i : su ~ 1)
for (j : 1 ~ sv)
f(u, i + j) = max(f(u, i + j), f(u, i) + f(v, j))
su = su + sv
return
乍一看合并两颗子树大小分别为 \(x,y\) 的子树的时间复杂度为 \(\mathcal O(xy)\)，所以总时间复杂度应为 \(O(n^3)\)。但是我们考虑到对于每一对结点，它被统计的次数只有一次，而这次统计是在转移它们 lca 时被统计的，所以可以得到时间复杂度 \(\mathcal O(n^2)\)。
但是，这并不是最终的时间复杂度，它还可以得到一个更优的上界：\(\mathcal O(nk)\)，其中 \(k\) 为背包值域。具体推导过程如下：
1. 如果一颗子树的 \(size > k\)，那么对于大于 \(k\) 的那部分背包是不需要的，即将其背包大小限制为 \(k\)。
2. 如果一颗子树的 \(size \leq k\)，不变。
3. 如果转移完一颗子树，它的 \(size \leq k\)，那么转移完整颗子树的时间复杂度为 \(\mathcal O(size^2) \leq \mathcal O(size\times k)\)，而对于若干个 \(size \leq k\) 的不相交子树，它们的 \(size\) 之和一定 \(\leq n\)，所以这一部分的时间复杂度为 \(\mathcal O(nk)\)。
4. 如果转移完一颗子树，它的 \(size > k\)，那么它的儿子有一些是 \(size \leq k\)，有一些是 \(size > k\)。对于不相交的 \(size > k\) 的子树，它的个数 \(\leq \dfrac{n}{k}\)，而合并一对的时间复杂度为 \(\mathcal O(k^2)\)，所以这一部分的时间复杂度为 \(\mathcal O(nk)\)；对于 \(size \leq k\) 的情况，如果目前合并到的 \(size > k\)，那么将其与剩下的 \(size \leq k\) 的儿子合并，时间复杂度为 \(\mathcal O(size \times k)\)，而 \(\sum size \leq n\)，所以这一部分的时间复杂度为 \(\mathcal O(nk)\)；如果要合并出 \(size > k\)，需要将已经合并出的最大的 \(size \leq k\) 与一个新儿子合并，时间复杂度 \(\mathcal O(k^2)\)，而这样的情况数 \(\leq \dfrac n k\)，所以这一部分的时间复杂度为 \(\mathcal O(nk)\)。
于是，我们推出了总的时间复杂度 \(\mathcal O(nk)\)。