hdu 2196 Computer (树的直径||树形dp)

2016年7月12日 0 作者 CrazyKK

hdu2196

题意：给出一棵树。。。求距离每个点的最远距离是多少。。。

思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？

1A.

 

 

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年07月12日 星期二 13时29分49秒
File Name :code/hdu/2196.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
int n,m;
vector < pi >edge[N];
int d[N];
int ans[N];
bool vis[N];
int beg,lst;
int far;
void bfs( int s)
{
    ms(d,0x3f);
    ms(vis,false);
    queue<int>q;
    q.push(s);
    vis[s] = true;
    d[s] = 0 ;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        int siz = edge[u].size();
        for ( int i = 0 ; i < siz;  i++)
        {
            int v = edge[u][i].fst;
            if (vis[v]) continue;
            vis[v] = true;
            d[v] = d[u] + edge[u][i].sec;
            q.push(v);
        }
    }
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
        while (~scanf("%d",&n))
        {
            ms(ans,0);
            for ( int i = 1 ; i <= n ; i++) edge[i].clear();
            for ( int i = 2 ; i <= n ; i++)
            {
                int u,v,w;
                u = i;
                scanf("%d %d",&v,&w);
                edge[v].push_back(make_pair(u,w));
                edge[u].push_back(make_pair(v,w));
            }
            bfs(1);
            int mx = 0;
            for ( int i = 1 ; i <= n ; i++)
            {
                if (d[i] > mx)
                {
                    mx = d[i];
                    lst = i ;
                }
            }
         //   cout<<"lst:"<<lst<<endl;
            far = 0 ;
            bfs(lst);
            for ( int i = 1 ; i <= n ; i++)
            {
                if (d[i]>far)
                {
                    far = d[i];
                    beg = i ;
                }
            }
         //   cout<<"far:"<<far<<endl;
         //   cout<<"beg:"<<beg<<endl;
            bfs(beg);
            for ( int i = 1 ; i <= n ; i++)
                ans[i] = max(ans[i],d[i]);
            bfs(lst);
            for ( int i = 1 ; i <= n ;i++)
                ans[i] = max(ans[i],d[i]);
            for ( int i = 1 ; i <= n ; i++)
                cout<<ans[i]<<endl;
        }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

20161201upd:更新一个dp的做法（虽然用树的直径搞貌似要更好想也更直观，不过为了体会dp的思想嘛。。。）

参考题解

 这道题要求的是从树上一点出发的最长路。考虑有根树，不难想到，从树上一点u出发的最长路必然是下述两种情况之一：
（1）第一步向下走，（一直向下，走到某叶子节点）
（2）第一步向上走。
考虑树形DP：
dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径
这里，次长路径的含义是：与某条选定的最长路径不重合的路径中最长的路径。
dp[2][u] : 从节点u第一步向上走所能获得的最长路径
注意：

考虑如何转移
对于节点u，考虑u的所有子节点v，用dp[0][v]来更新dp[0][u], dp[1][u]。
至于dp[2][u], 仍考虑两种情况：
（1）第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。
这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:（kk:因为如果第一步向上走，然后又从父亲节点回到当前节点，那么这是无意义，并且等于没有更新向上走的情况，这也是要求次小的原因）如果从f第一步走到u能走出一条从f向下的最长路，就用dp[1][f]来更新dp[2][u]，否则用dp[0][f]。
（2）第二步仍向上走，这样便转移到f第一步向上走的情况，即dp[2][f]。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年12月01日 星期四 09时03分08秒
File Name :code/hdu/r2196.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
int n;
vector < pi > edge[N];
int dp[3][N];
//dp[0][i]:从节点i出发第一步向下走能达到的最远距离。
//,dp[1][i]：从节点i出发第一步向下走，能达到的次远距离（要求与最远距离的路径不相交）
//dp[2][i]:从节点i出发第一步向上走，能达到的最远距离。
void dfs( int u,int pre)
{
    for ( auto x : edge[u])
    {
        int v = x.fst;
        int w = x.sec;
        if (v==pre) continue;
        dfs(v,u);
        if (w+dp[0][v]>dp[0][u])
        {
            dp[1][u] = dp[0][u];
            dp[0][u] = w + dp[0][v];
        }else if (w + dp[0][v]>dp[1][u])
            dp[1][u] = w + dp[0][v];
    }
}
void dfs2( int u,int pre)
{
    for ( auto x : edge[u])
    {
        int v = x.fst;
        int w = x.sec;
        if (v == pre) continue;
        if (w + dp[0][v]==dp[0][u])
            dp[2][v] = max(dp[2][v],dp[1][u] + w);
        else dp[2][v] = max(dp[2][v],dp[0][u] + w);
        dp[2][v] = max(dp[2][v],dp[2][u] + w);
        dfs2(v,u); //调用成了dfs，调试了半天。。。智力－２
    }
}
int main()
{
#ifndef  ONLINE_JUDGE
    freopen("code/in.txt","r",stdin);
#endif
    while (~scanf("%d",&n))
    {
        ms(dp,0);
        for ( int i = 1 ; i<= n ; i++) edge[i].clear();
        for ( int i = 2 ;i  <= n ; i++)
        {
            int u,v,w;
            u = i ;
            scanf("%d %d",&v,&w);
            edge[u].push_back(MP(v,w));
            edge[v].push_back(MP(u,w));
        }
        dfs(1,-1);
        dfs2(1,-1);
        for ( int i = 1 ; i <= n ; i++) printf("%d\n",max(dp[0][i],dp[2][i]));
    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}
 
 
 
 

 

 

分类目录hdoj
标签树形dp 树的直径

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz