树形DP图画入门题解2 （HDU2196）

http://acm.hdu.edu.cn/showproblem.php?pid=2196 题意：一棵树N个节点，每条边有一个权w，求每个节点距离最远的路径长度。 2次深搜： 【第一次深搜】：求出在节点u的子树中，离u的最远，次远距离， 并标记 是从哪儿来的 。 int max_lenth[u] , max_id[u] ;

http://acm.hdu.edu.cn/showproblem.php?pid=2196

题意：一棵树N个节点，每条边有一个权值w，求每个节点距离最远的路径长度。

2次深搜：

 【第一次深搜】：求出在节点u的子树中，离u的最远，次远距离， 并标记是从哪儿来的。

int max_lenth[u] , max_id[u] ;      最远距离， 转移儿子节点
int second_lenth[u] , second_id[u] ;  次远距离， 转移儿子节点

图1 ：  第一次深搜， 当节点1的子树（绿色部分）遍历完回退的时候，最远次远距离只能是从（红色部分）2,6,9过来， 

          转移儿子节点就在2,6,9中选择。  也就是说max_id【1】 , second_id【1】 中存储的是2,6,9 中的某个。

图2 ：  第一次深搜， 当节点2的子树（绿色部分）遍历完回退的时候，最远次远距离只能是从（红色部分）3,5过来， 

          转移儿子节点就在3,5中选择。  也就是说max_id【2】 , second_id【2】 中存储的是3,5 中的某个。

【第二次深搜】 ： 求每个节点在整棵树上的最远、次远距离

图3 ：  先看状态转移：

          对于节点2 ， 最远距离、次远距离，来自2个地方（绿色部分）。

          绿色区域1、 节点2的子树部分，这个在第一次深搜已经保存好在绿色区域1离节点2的最远、次远距离。

          绿色区域2、 节点2的父亲节点1+父亲节点1的子树部分，这个在第一次深搜已经保存好在绿色区域2离节点1的最远、次远距离。

       那么只需要做个比较即可更新。

情况1 。  节点max_id[1] = 2，1的最远距离来自2 。 那么区域2中离节点2的最远距离second_lenth[1]。

             即  max_lenth[2] = max( max_lenth[2] , second_lenth[1] + w(1,2)) 。 

情况2 。  节点max_id[1] ！= 2，1的最远距离不是来自2 。 那么区域2中离节点2的最远距离max_lenth[1]。

             即  max_lenth[2] = max( max_lenth[2] , max_lenth[1]+w(1,2)) 。 

注意（树形DP最值得注意的地方）： 

      dfs_1  ， 先递归再DP

      dfs_2 ,   先DP再递归 

 

const int Max_N = 10008 ;

struct Edge{
       int v ;
       int w ;
       Edge(){}
       Edge(int i , int j):v(i) , w(j){}
};

vector<edge> List[Max_N] ;
int N ;
int max_lenth[Max_N] , max_id[Max_N] ;
int second_lenth[Max_N] , second_id[Max_N] ;

void dfs_1(int u , int father){
     int i , w , v ;
     for(i = 0 ; i <br>
<br>


</edge>