思路来自 Konata，有删改及本作者的想法。

如果正常想，每个节点都要进行 \(O(n^2)\) 的背包，则时间复杂度为 \(O(n^3)\)，其实不然。

假设 \(n\) 个节点的树形背包的时间复杂度为 \(f(n)\)。

那么假设根节点下面的子树大小分别为 \(p_1,p_2,\dots,p_k\)，子树大小 \(p_i\) 对应的子树根节点下面的子树大小分别为 \(g_{i,1},g_{i,2},\dots,g_{i,s_i}\)。

\[\begin{aligned}f(n) &=\sum\limits^k_{i=1}f(p_i)+\sum\limits^k_{i=2}\left(p_i\times\sum\limits^{i-1}_{j=1}p_j\right) \\ & = \sum\limits^k_{i=1}f(p_i)+\sum\limits_{1\leqslant i<j\leqslant k}p_i\times p_j \\ & = \sum\limits^k_{i=1}f(p_i)+\dfrac{\left(\sum\limits^k_{i=1}p_i\right)^2-\sum\limits^k_{i=1}p_i^2}{2} \\ & = \dfrac{1}{2}(n-1)^2+\sum\limits^k_{i=1}f(p_i)-\dfrac{1}{2}\sum\limits^k_{i=1}p_i^2 \\ & \leqslant \dfrac{1}{2}n^2+\sum\limits^k_{i=1}(f(p_i)-\dfrac{1}{2}p_i^2) \\ & = \dfrac{1}{2}n^2+\sum\limits^k_{i=1}(\dfrac{1}{2}(p_i-1)^2+\sum\limits^{s_i}_{j=1}(f(g_{i,j})-\dfrac{1}{2}g_{i,j}^2)-\dfrac{1}{2}p_i^2) \\ & \leqslant \dfrac{1}{2}n^2+\sum\limits^k_{i=1}\sum\limits^{s_i}_{j=1}(f(g_{i,j})-\dfrac{1}{2}g_{i,j}^2) \\ & \leqslant \dfrac{1}{2}n^2+\sum\sum\dots\sum(f(\dots)-\dfrac{1}{2}(\dots)^2) \\ & \leqslant \dots \\ & \leqslant \dfrac{1}{2}n^2 \\ & =O(n^2) \end{aligned}\]

特殊得，如果背包的容量上限为 \(V\)，则总时间复杂度为 \(O(nV)\)。