。。 好题。。无限仰慕宋神牛。。。 首先： 节点数-高度 ≤ k 什么意思呢？ 就是背包容量为 k。。。然后其中一条链可以免费取。。。 。。设这条链为 free chain 。然后就可以 O(n3) 了。。。 g[u][i]: 以 u 为根的子树。。。 容量为 i。。。 f[u][i]: 以 u 为根的子树。。u 在 free chain 上。。 容量为 i。。。 https://vijos.org/records/5411e2a348c5fc1e1c8b4568 我们发现 g[][] 就是选课。。。https://vijos.org/records/54062d6048c5fcbb348b4……