结论：若树上背包的上限为 \(k(k\le n)\)，时间复杂度为 \(O(nk)\)。
参考实现：
dfs(u) {
sz[u] = 1; init(f[u]);
for (v : son[u]) {
dfs(v);
for (i = 0; i <= k and i <= sz[u])
for (j = 0; i + j <= k and j <= sz[v])
upd(f[u][i + j], f[u][i], f[v][j]);
sz[u] += sz[v];
}
}
证明（参考了这一篇）：
考虑令 \(sz_u\le k\) 的子树 \(u\) 为小子树，否则为大子树。
称 \(fa_u\) 为大子树而 \(u\) 为小子树的子树 \(u\) 为极小大子树。
称 \(v\in son_u\) 均为小子树而 \(u\) 为大子树的 \(u\) 为极大小子树。
性质 \(1\)：
令极小大子树的子树的根分别为 \(R_{1\sim c}\)。
那能保证对于 \(1\le i < j\le c\)，\(R_i\) 和 \(R_j\) 子树内的点不重，因为其肯定不为包含关系且两点在同一颗在树上。
所以 \(\sum\limits_{i = 1}^m sz_{R_i}\le n\)，又因是大子树所以 \(sz_{R_i} > k\)，所以 \(c < \lfloor\frac{n}{k}\rfloor\)。
性质 \(2\)：
令极大小子树的子树的根分别为 \(U_{1\sim m}\)。
那能保证对于 \(1\le i < j\le m\)，\(U_i\) 和 \(U_j\) 子树内的点不重，同上。
所以有 \(\sum\limits_{i = 1}^m sz_{U_i} \le n\)。
首先考虑小子树内部的合并。
考虑把这些都归到极大小子树 \(u\) 上。
若 \(A, B\) 两部分合并，那对应的时间复杂度为 \(O(sz_A\times sz_B)\)，那考虑把这个贡献拆为 \(A\) 子树中的点 \(u\) 与 \(B\) 子树中的点 \(v\) 在这里的合并。
那么每两个点都只会产生一次贡献，所以 \(u\) 子树产生的贡献是 \(O(sz_u^2)\)。
那么时间复杂度为 \(O(\sum\limits_{i = 1}^m sz_{U_i}^2)\)。
因为对于 \(x > y, c > 0\)，\((x + c)^2 + (y - c)^2> x^2 + y^2\)，且根据性质 \(2\) 有 \(\sum\limits_{i = 1}^m sz_{U_i} \le n\)。
所以 \(\sum\limits_{i = 1}^m sz_{U_i}^2\le k^2\times \frac{n}{k} = nk\)，所以这部分时间复杂度为 \(O(nk)\)。
考虑小子树与大子树的合并。
发现这肯定只会发生在极大小子树 \(u\) 和其父亲 \(fa_u\) 上。
那么这次合并时间复杂度为 \(O(k\times sz_u)\)。
总的时间复杂度就为 \(O(k\times \sum\limits_{i = 1}^m sz_{U_i})\)。
根据性质 \(2\) 有 \(\sum\limits_{i = 1}^m sz_{U_i} \le n\)，所以时间复杂度为 \(O(nk)\)。
考虑大子树和大子树的合并。
那么每次合并的复杂度就是 \(O(k^2)\) 的。
发现本质上还是极小大子树的合并，所以合并次数 \(=\) 极小大子树数量 \(-1\)。
又根据性质 \(1\) 有 \(c < \lfloor\frac{n}{k}\rfloor\)，所以总时间复杂度 \(O(\frac{n}{k}\times k^2)\) 即 \(O(nk)\)。
综上，时间复杂度为 \(O(nk)\)。