树形dp专题

树形dp专题

入门：

1. HDU 1520 Anniversary party子节点和父亲节点不能同时选，问最大价值。 题解
2. HDU 2196 Computer 求树上每个点能到达的最远距离 。题解
3. Godfather 求树的重心（删除该点后子树最大的最小）。题解
4. POJ 3107 Tree Cutting 求删除哪点后子树最的小于等于节点总数的一半。
5. POJ 3140 Contestants Division 删除某边后剩余两个分支差值最小是多少

进阶：

1. HDU 3586 Information Disturbing 给定一个带权无向树，要切断所有叶子节点和1号节点（总根）的联系，每次切断边的费用不能超过上限limit，问在保证总费用<=m下的最小的limit
2. POJ 3162 Walking Race 一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最大距离和最小距离的差小于M，问怎么取使得天数最多？
3. HDU 5834 Magic boy Bi Luo with his excited tree 每个节点有一个价值Vi，每走一次一条边要花费Ci，问从各个节点出发最多能收获多少价值。题解
4. POJ 2152 Fire n个节点组成的树，要在树一些点上建立消防站，每个点建站都有个cost[i]，每个点如果不在当前的点上建站，也要依赖其他的消防站，并且距离不超过limit[i]。求符合上述条件的最小费用建站方案。
5. POJ 1741 Tree 求树上距离小于等于K的点对有多少个。