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

php中文网

发布： 2016-06-07 15:49:54

原创

1287人浏览过

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] ; 次远距离，转移儿子节点

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

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

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

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

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

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

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

爱改写

AI写作和改写润色工具

查看详情

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

图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 < 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) ;
               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 ;
}

登录后复制