最近做的题里面出现了好几道树形DP比较，经典，有个类型的题目我写错了好多遍，最后终于查出来了，顺便就写个小结纪念一下。
大概树上的DP主要围绕树的直径，树上节点到其他点的最远距离这样两点展开，树的直径的就是两遍DFS，（或者BFS），然后后一个类型，需要两边DFS来把想要的信息转移，得到最后的结果，（这就是树这种数据结构的好处），转移过程自己总结一下，细心一点即可，我觉得我写错的那个类型的题目完全是不够细心。。。
下面是几道题目：
1. Time to live http://codeforces.com/gym/100274/attachments
这题是可以数DP的，当然分析一下会简单一些，问题要求树上点到其他点的最远距离的最小值，不想写树DP的话就分析一下，发现我们找到树的直径，然后答案就是直径+1的一半，（取整）。当然我还是写了树DP因为这是一个很经典的问题，这题虽然是只求最远距离的最小值，但是更多的题目中是需要知道每个点的到其他点的最远距离。我们先一遍DFS保存每个节点子树的最大深度（也就是最远距离），然后再做一遍DFS转移即可，DFS转移要细心写，在纸上画出来会好些。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#pragma warning (disable : 4996)
#define N 111111
#define mem(a) memset(a, 0, sizeof(a))
#define LL long long
#define sl(a) strlen(a)
using namespace std;
int fi[N], ne[2 * N], en[2 * N], tot, dm[N];
void add(int x, int y){
ne[++tot] = fi[x], fi[x] = tot, en[tot] = y; //邻接表
}
void dfs(int x, int p){
dm[x] = 0;
for (int go = fi[x]; go; go = ne[go]){
if (en[go] != p){
dfs(en[go], x);
dm[x] = max(dm[x], dm[en[go]] + 1); //其实如果边有权，加的就不是1了
}
}
}
void dfs1(int x, int p, int fm){ //转移，这个转移是个很经典的转移，当父亲向儿子传递信息时，
//需要先记录，记录他的的子节点在第一次dfs传给他的值中的最大的和次大的两个值，以及这个父节点的父亲
//传给他的信息，在所有这些信息里面取两个较大的作为最大和次大，作为有用信息
int m1 = fm, m2 = 0, id1 = p;
for (int go = fi[x]; go; go = ne[go]){
if (en[go] != p){
if (dm[en[go]] + 1 >= m1) m2 = m1, m1 = dm[en[go]] + 1, id1 = en[go];//这里在记录最大和次大，关键这里千万不能写错
//dm[en[go]]是他地子节点原来的最大深度，到他本身显然要加1
else if (dm[en[go]] + 1> m2) m2 = dm[en[go]] + 1;
}
}
for (int go = fi[x]; go; go = ne[go]){
if (en[go] != p){
if (en[go] != id1) {//这个节点不是原来把最大深度贡献给父节点的点
dm[en[go]] = m1 + 1; //然后传递给子节点这里又得加一，道理是一样的，但是原来写的时候疏忽了，想当然以为前面加过了，wa成狗
dfs1(en[go], x, m1 + 1);//然后把自己信息也作为父节点信息传下去
}
else {//这个节点时原来使父节点获得最大深度的节点这是他不能取父节点的m1，而只能取m2与他当前本身这两个的较大值
dm[en[go]] = max(dm[en[go]], m2 + 1);
dfs1(en[go], x, m2 + 1);
}
}
}
}
int main(){
int ca = 1, i, j, k, l, n, t, tem, num, re, d, x, y;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (i = 0; i < n - 1; ++i){
scanf("%d%d", &x, &y);
x++, y++;
add(x, y), add(y, x);
}
dfs(1, 0);
//for (i = 1; i <= n; ++i) cout << dm[i] << ' ';
//cout << endl;
dfs1(1, 0, 0);
//for (i = 1; i <= n; ++i) cout << dm[i] << ' ';
//cout << endl;
for (i = 1, re = n + 1; i <= n; ++i) re = min(re, dm[i]);
printf("%d\n", re);
mem(dm), mem(fi), mem(ne), mem(en), tot = 0;
}
return 0;
}
2. SGU 149 Computer Network http://acm.sgu.ru/problem.php?contest=0&problem=149
这题就是需要把每个点到树上最远距离这一信息全部求出来的，代码基本一样，不多说。
3. SGU 143 Long Live the Queen http://acm.sgu.ru/problem.php?contest=0&problem=143
这题需要求出以每个节点为根的不完全子树的权值最大值，每个节点都维护这个信息即可，转移也比较简单。
4. USTCOJ 1352 传送带 http://acm.ustc.edu.cn/ustcoj/problem.php?id=1352
这题咋一看像有向图，其实还是看出无向图做，保存每个节点为根的子树需要改变的边的最小值即可。
下面是几道难度比前面稍大的题：
5. HDU 3721 Building Roads http://acm.hdu.edu.cn/showproblem.php?pid=3721
O（n^2）算法，枚举断的边，然后做树DP，但是树DP出的结果不一定最优，要想清楚。。。不要轻易下结论。（也可以先找直径，再枚举断的边，断的最优的边一定在直接上）
6. HDU 4661 Message Passing http://acm.hdu.edu.cn/showproblem.php?pid=4661
需要比较多的数学推导，拓扑排序数问题，树上的转移比较难写，好题！
7. HDU 4679 Terroist's destroy http://acm.hdu.edu.cn/showproblem.php?pid=4679
利用树的直接性质好做些，O(n).
差不多就先这些吧。