树形dp
树形
在看本章之前，建议您先学会邻接链表，邻接矩阵，链式前向星等等
包括得知道什么是树！！！如何存树！！！
-
树的直径：给一棵树，求树上的最长链。
-
树的重心：给一棵树，求树的重心，即删掉某个点后剩下的最大连通块大小最小。
由于树形DP没有任何的模板，规律可循，我们马上看到例题来分析，关于树形DP的题目：
【例题1】题目传送门
Ural大学有
该问题的解：博客直接访问更优
如果这一题，没有“如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了 ”这一句话大家都肯定会做，明显的直接求和嘛。
Q:那如果加上了这一条，又要怎么做呢？
A:明显的树形DP嘛……
同样的，我们首先要把树先建立起来，按照题目样例，建立起来大概是这个样子：（图画的很丑，自己理解一下就好了）
按照题目的意思，如果
那么，我们可以根据这个性质，设置两个数组：
那么再回来看样例，对于
-
f[5]=r[5]+g[3]+g[4] -
g[5]=max(f[3],g[3])+max(f[4],g[4])
解释：
自然，对于每个状态的转移方程就好推了：
-
f[$父节点$]=r[$父节点$]+g[$子节点$]+g[$子节点$] -
g[$父节点$]=max(f$[子节点$],g[$子节点$])+max(f$[子节点$],g[$子节点$])
当然了，样例建立出来的树刚好是二叉树，所以：
-
f[$父节点$]=r[$父节点$]+g[$子节点$]+$……$+g[$子节点$] -
g[$父节点$]=max(f$[子节点$],g[$子节点$])+$……$+max(f$[子节点$],g[$子节点$])
再来考虑：
- 初始化：
f[0 ~n]=0 - 答案：
f[ 根节点]
这题不就做出来了吗？
*然后确定根节点的话，可以利用$n(n+1)/2
【例题2】（由于本题的提交网站需要账号登录才能进入，无法注册账号，你们无法提交啊……
政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。
任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。
告诉你每个火车站的利润，问你可以获得的最大利润为多少。
该问题的解：博客直接访问更优
其实从题目上来说，很容易想到贪心，我们又很迅速的排除这种想法，（因为贪心是贪心当前一个子树的最大利润，它是局部最优解逐渐扩散到整体最优解）
这样的一道题，不能贪心，只能DP（树形DP）
Q: 既然要树形DP，你的根节点在哪呢？？？
A: 不难知道根节点可以任取一点，我们这里就当结点1为根节点
我们先把树先建立一下：
（by xx330312）
Q:如果是这样的话，那么状态又是怎样的呢？（重点重点，敲黑板）
A:
- 设
f[i] 表示不取第i 号节点利润的最大利润 - 设
g[i] 表示取第i 号节点利润的最大利润
看回上面那个图，我们假设当前在三号结点：
- 如果不取第
3 号节点利润，那么答案就在max( 不取第2 号节点利润的最大利润， 取第2 号节点利润的最大利润) ，以及max( 不取第4 号节点利润的最大利润， 取第4 号节点利润的最大利润) 之和 - 如果取第
3 号节点利润，那么答案就在取第2 号节点利润的最大利润，以及取第4 号节点利润的最大利润之和
尝试把它们转换成代码：
-
f[3]+=max(f[2],g[2])+max(f[4],f[4]) -
g[3]+=f[2]+f[4]
当然了，这只是对于三号结点，我们再把它换成第
-
f[i]+=max(f[i$的子节点$],g[i$的子节点$])+……+max(f[i$的子节点$],g[i$的子节点$]) -
g[i]+=f[i$的子节点$]+……+f[$i的子节点$]
这就是状态转移方程。
我们再来考虑初始化：
因为
也就是：
-
f[i]=0 -
g[i]=s[i]
Q:对了，你好像没有告诉我最后答案是啥……
A:最后答案其实也不难想到：
答案必为
整道题就讲完了，要然后也没有然后了……
【例题3】题目传送门
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 NN 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 MM 门课程学习，问他能获得的最大学分是多少？
该问题的解：
看到这一题，这道题因为正常动态规划可能做不了，根据若课程
构图：
其实构图的方式也很简单，对于一个
Q:但是你会发现……有时候构建的不止有一棵树，而是森林啊！！！
A:无论会不会出现森林情况，只要你把每棵树都往一个超级根节点