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 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 < List[u].size() ; i++){          v = List[u][i].v ;          w = List[u][i].w ;          if(v == father)              continue ;          dfs_1(v , u) ;          if(second_lenth[u] < max_lenth[v] + w){                second_lenth[u] = max_lenth[v] + w ;                second_id[u] = v ;                if(max_lenth[u] < second_lenth[u]){                     swap(max_lenth[u] , second_lenth[u]) ;                     swap(max_id[u] , second_id[u]) ;                }          }     }}void  dfs_2(int u , int father){      int i , v , w ;      for(i = 0 ; i < List[u].size() ; i++){           v = List[u][i].v ;           w = List[u][i].w ;           if(v == father)               continue ;           if(v == max_id[u]){               if(second_lenth[v] < second_lenth[u] + w){                    second_lenth[v] = second_lenth[u] + w ;                    second_id[v] = u ;                    if(max_lenth[v] < second_lenth[v]){                         swap(max_lenth[v] , second_lenth[v]) ;                         swap(max_id[v] , second_id[v]) ;                    }               }           }           else{               if(second_lenth[v] < max_lenth[u] + w){                    second_lenth[v] = max_lenth[u] + w ;                    second_id[v] = u ;                    if(max_lenth[v] < second_lenth[v]){                         swap(max_lenth[v] , second_lenth[v]) ;                         swap(max_id[v] , second_id[v]) ;                    }               }           }           dfs_2(v , u) ;      }}int  main(){     int i , u , v , w ;     while(scanf("%d" ,&N) != EOF){          memset(max_lenth , 0 , (N+1)*sizeof(int)) ;          memset(second_lenth , 0 , (N+1)*sizeof(int)) ;          for(i = 1 ; i <= N ; i++) List[i].clear() ;          for(u = 2 ; u <= N ; u++){               scanf("%d%d" ,&v ,&w) ;       <i>本文来源gaodai$ma#com搞$代*码*网</i>        List[u].push_back(Edge(v,w)) ;               List[v].push_back(Edge(u,w)) ;          }          dfs_1(1 , -1) ;          dfs_2(1 , -1) ;          for(i = 1 ; i <= N ; i++)              printf("%d\n" , max_lenth[i]) ;     }     return 0 ;}

喜欢 (0)赏

[搞代码]

分享 (0)