当前位置:Gxlcms > mysql > 树形DP图画入门题解2(HDU2196)

树形DP图画入门题解2(HDU2196)

时间:2021-07-01 10:21:17 帮助过:45人阅读

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

人气教程排行