树，一种十分优美的数据结构，因为它本身就具有的递归性，所以它和子树间能相互传递很多信息，还因为它作为被限制的图在上面可进行的操作更多，所以各种用于不同地方的树都出现了，二叉树、三叉树、静态搜索树、AVL树，线段树、SPLAY树，后缀树等等..
枚举那么多种数据结构只是想说树方面的内容相当多，本专辑只针对在树上的动态规划，即树形DP.做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分，这个也没一般性的东西可讲，因为每道题目要求做的事都不尽相同。
这个专辑暂时分为 3 个部分，分的可能不是很好，后面题目做多了理解更深了可能会更改，但那都是后话了。
一、常规树形DP#
1、 Hdu 1520 Anniversary party 每个节点有权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？解题报告Here
[ ](http://acm.hdu.edu.cn/showproblem.php?pid=1011)[2、Hdu 2196 Computer](http://acm.hdu.edu.cn/showproblem.php?pid=2196) 经典题，求树每个点到其他点的最远距离，转化为有根树，深搜两次，一次记录到叶子的最远距离，一次更新最终答案。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7642536)
[ ](http://acm.hdu.edu.cn/showproblem.php?pid=1011)[3、Poj 1741 Tre](http://poj.org/problem?id=1741)[e](http://acm.hdu.edu.cn/showproblem.php?pid=2196)(难) 经典题，求树上两点间距离小等于K的方案数，树上分治。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7723400)
[ 4、Poj 2152 Fire（难） ](http://poj.org/problem?id=2152) 罕见的O(n^2)的树形DP，在树上建消防站，要求每个节点离最近的消防站距离小于K，问最小花费。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7725917)
[ 5、Poj 3162 Walking Race（难） ](http://poj.org/problem?id=3162) 树形DP找最远距离+线段树查询最大最小值，然后再维护两个指针遍历整个序列。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7727677)
[6、cf 218D. Choosing Capital for Treeland ](http://www.codeforces.com/problemset/problem/219/D)把边方向转变成边权，正向为0，反向为1.经过转换，问题变成求某点为根到所有点的边权总和，求边权总和最小的那些点。
二、树形背包问题(在树上进行分组背包处理)#
1、Poj 1155 TELE 把每个节点的子节点看成一组背包，最大容量是这点的叶子子孙数量，选几个节点就是选择的容量，价值就是用户给的Money-中转费用。解题报告Here
[ 2、Hdu 1011](http://acm.hdu.edu.cn/showproblem.php?pid=1011)[ Starship Troopers](http://acm.hdu.edu.cn/showproblem.php?pid=1011) 和上题相似，要选择父节点必先子节点，特判m为0的时候。
[ 3、Poj 1947 Rebuilding Roads](http://poj.org/problem?id=1947) 求最少删除几条边使得子树节点个数为p，具体的模型和上题很像。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7632785)
[ 4、Hdu 1561 The more, The Better](http://acm.hdu.edu.cn/showproblem.php?pid=1561) 在一棵树上选择若干个点获得的最大价值，选子节点必须先选父节点，求解情况和上两题相同。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7637847)
[5、Hdu 4003 Find Metal Mineral](http://acm.hdu.edu.cn/showproblem.php?pid=4003) (推荐，好题) 树形DP+选且只能选一个物品的分组背包，状态转移方程难想。解题报告[here](http://http//blog.csdn.net/woshi250hua/article/details/7648099)
[ 6、Poj 2486 Apple Tree](http://poj.org/problem?id=2486) 树形DP+分组背包，但是状态转移方程要分三步，较为难想。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7648798)
[7、Poj 3345 Bribing FIPA](http://poj.org/problem?id=3345) 树形DP+分组背包，和前面几题相比没有特殊的地方，只是要注意输入。具体可见**[Here](http://blog.csdn.net/woshi250hua/article/details/7684771)**
[8、Hdu 4044 GeoDefense](http://http//acm.hdu.edu.cn/showproblem.php?pid=4044) 树形DP+分组背包，要求从每个儿子结点获取最小的hp，然后找这些儿子的最大组合，不是特别好想。解题报告见[Here](http://blog.csdn.net/woshi250hua/article/details/7683765)
[9、Zoj 3627 Treasure Hunt II ](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3626) 树形DP +分组背包，浙大月赛的水题，很普通的树形背包。
[10、4276 The Ghost Blows Light](http://acm.hdu.edu.cn/showproblem.php?pid=4276) 有两种写法，一种是把一棵树压缩成一条链，然后在链上DP，一种和 Apple tree差不多，具体见[Here](http://blog.csdn.net/woshi250hua/article/details/7958770)
三、删点或者删边类树形DP#
1、Hdu 3586 Information Disturbing 二分Upper power limit，然后从叶子节点向上更新，边权与limit比较再进行状态转移。解题报告Here
[2、Poj 3107 Godfathe](http://poj.org/problem?id=3107)r 删点，使剩下的分支中最大的节点数最小，深搜一次记录到叶子节点距离，再进行枚举求最大值，再更新答案。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7684182)
[3、Poj 2378 Tree Cutting](http://poj.org/problem?id=2378) 删点，使剩下的分支中有最大节点数的分支小等于总数一半，问有几种方案，和上题差不多。解题报告[Here ](http://blog.csdn.net/woshi250hua/article/details/7710339) [ ](http://poj.org/problem?id=3107)
[4、Poj 1655 Balancing Act ](http://poj.org/problem?id=1655) 删点，使剩下的分支中最大的节点数最小，深搜一次记录到叶子节点距离，再进行枚举求最大值，再更新答案。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7710343)
[5、Poj 3140 Contestants Division](http://poj.org/problem?id=3140)[ ](http://poj.org/problem?id=1655) 删边，求删去某条边后两个分支的最小差异值，也是深搜两次。解题报告[Here](http://blog.csdn.net/woshi250hua/article/details/7710541)
#
这篇文章将会不断更新，以后每遇到树形DP我都会整理进这个专题，希望大家保持关注。
本文ZeroClock原创，但可以转载，因为我们是兄弟。
顶
13