树型DP专题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

总结一下我做过的树型DP题目,没有固定的分析和模板,因为DP也可能搞出模板了,所以直接将题目归类,以具体题目来分析

树上求最长链

树dp + 背包

树dp+背包是最常见的一种模型,而且也是相对较难的,但好处是,套路比较固定,如果熟悉背包的滚动数组写法,又能看出是背包模型,那么代码实现并不难

树上的支配性问题

树的重心 分治在树上的应用

关系树的重心的一些基本概念和定义:

  1. 如果只是单纯求树的重心,那是比较简单的,有固定模板可以求
  2. 求树的重心可以联系到分治的思想,是一类比较难的类型

其他类型

简单:

较难: