树形dp汇总(树形结构的动态规划)

动态规划——树形dp

写在前面的话

既然来看这篇文章，相信肯定都知道动态规划是什么吧
不知道就请出门左拐找度娘了。。。

fake tyher%%%
fake tyher%%%//不要误会，与博客无关

树形dp简介

简单来说，树形dp就是在树上进行dp(你就当这是废话)
一般对于一些题目，如果树上的儿子与父亲存在一些特定的关系(类似于线性dp里i和j的关系)，那么我们可以考虑用树形dp来完成相关的指令(ans)
再通俗一点，就是假如你把一棵树的一条链抠出来，可以用线性dp的方法直接做，那么一般可以考虑树形dp，而树形dp就是这种“想法”的“升级版”。。。
ps：前面的话如果实在没有懂(其实应该可以知道是什么吧)，你就当我放了个屁

一般方法(结合例题看)

树形dp不同于其他dp的就是它的方法没有那么多变，一般也就那几个套路，只是维护起来麻烦的问题

• 判断：
  
  1. 一般那种很明显的儿子与爸爸存在dp关系的题目
  2. 把链抠出来任意一条可以找到线性类型的dp关系的题目(比较片面)
  3. 感(biao)觉(qian)就是的题目
• 做法
  
  1. 找到爸爸与儿子的dp关系式(一般答案在dp[根])
  2. 从根开始Dfs，回溯的时候转移(这个地方随机应变吧，就是抽象为线性dp的转移方程啊)
  3. 一般要考虑容斥等东西(容斥的话就是万一我的dp方程可以从爸爸转移过来呢？)(暂时不用理解)

从例题入手

luogu2014选课

题目简介

给定一棵树(先修课连向普通课)，求在选了儿子就必须选爸爸的条件下，选出m个点，点权和(学分)最大

方法

根据我上面的一般方法来：

• 先摆出状态再看怎么来的
  设dp[i][j]表示以i为根的子树选了j门课的最大点权和(学分)
• 因为选了儿子必须选爸爸，那么儿子的状态确定后(最大学分)，爸爸转移的一种方式就确定了
• 那我们考虑转移(父节点:now，儿子节点:qw)
  先看转移再解释：(j,k为枚举的选的课的数量)(暂时没有算上选now的值)
  dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[qw][k])
• 显然，我如果在之前的儿子上转移出来了dp[now][j-k]，那么和dp[qw][k]拼起来就是想要的状态了，但是注意一点：我们只是还没有把now的权值加进去，但是我们要假设它加进去了，以便转移，转移完之后再统一加上：dp[now][j]+=v[now](枚举j)
• 完整的代码：Junlier选课

总结

其实已经可以结束了
其他的题目上洛谷找标签就有一版
所以，溜了溜了。。。