CF161D Distance in Tree + 树上背包

DP状态定义

根据子树位置路径长度的统计设计状态。

表示在以 为根的子树中，到 的距离恰好为 的节点个数。

初始化

状态转移方程式

在合并子树时来统计答案

处理完答案后再合并子树：

戳我看代码

最重要的，树上背包！

例题：[CTSC1997] 选课

状态定义

表示在 这里，前 棵子树，共计选择 门课，共可以获得的最大贡献。

状态转移

自己先想想，很简单，或者看代码。