树形DP杂题选讲（会不断更新）
重建道路
这是一道比较基础的树上背包。
可以设计状态 dp[ u ][ i ] 表示在以 u 为根的子树内 ，只含有 i 个节点需删去的边的最少数量。
可以推出， u 的状态可以通过子节点 v 的状态来刷新，因为 u 此时不包含 v 的子树 ，所以 u , v 之间没有边。 加上 v 子树后 ，u 和 v 有连边 ， 所以每转移时 ， 状态需 -1 。
可推出 转移方程 ： dp[ u ][ i ] = min( dp[ u ][ i-j ] + dp[ v ][ j ] -1 )
初始化 ： dp[ u ][ 1 ] = u 的入度
世界杯
设计状态 dp[ u ][ i ] 表示从节点 u 到根不选 i 场比赛的 符合条件 u 子树中的最小点权和。
那么对于更新 u 状态时，有选 u 节点和不选两种情况 ， 可推出转移方程
dp[ u ][ i ]=min( dp[ lson[ u ] ][ i ] + dp[ rson[ u ] ][ i ] + w[ u ] , dp[ lson[ u ] ][ i + 1 ] + dp[ rson[ u ] ][ i + 1 ] )