算法：HDU 2196 Computer（树形dp经典）

算法：HDU 2196 Computer（树形dp经典）2014-01-01 csdn shuangde800题意：

给出一棵树，求离每个节点最远的点的距离

思路：

把无根树转化成有根树分析，

对于上面那棵树，要求距结点 2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1

还有知道2的父节点1为根节点的树Tree（1）-Tree（2）部分（即红色圈起部分），距离结点1 的最长距离+dist（1,2） = L2，那么最终距离结点2最远的距离就是max{L1，L2}

f[i][0],表示顶点为i 的子树的，距顶点i的最长距离

f[i][1],表示Tree（i的父节点）-Tree（i）的最长距离+i跟i的父节点距离

要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。

然后要求 f[i][1], 可以从父节点递推到子节点，

假设节点u有n个子节点，分别是v1,v2...vn

那么

如果vi不是u最长距离经过的节点，f[vi][1] = dist（vi,u）+max（f[u][0], f[u][1]）

如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,

可得f [vi][1] = dist（vi, u） + max（secondDist, f[u][1]）