SGU 149 Computer Network 树DP/求每个节点最远端长度

一个比较经典的题型，两次DFS求树上每个点的最远端距离。

参考这里：http://hi.baidu.com/oi_pkqs90/item/914e951c41e7d0ccbf904252

dp[i][0]表示最远端在以 i 为根的子树中的最长长度，dp[i][1]记录最远端在以i为根的子树中的次长长度，dp[i][2]表示最远端不在以 i 为根的子树中的最长长度。

答案即为max( dp[i][0], dp[i][2] );

dp[i][0]和dp[i][1]可以通过一次DFS得到。

再看dp[i][2], 设fa[i]为节点 i 的父节点: dp[i][2] = max( dp[ fa[i] ][2], dp[ fa[i] ][0] ) + dis[ fa[i] ][i];

显然，如果dp[ fa[i] ][0] 中的最长长度是由dp[i][0]状态转移得到的，上面的结论就不对了。

于是我们还需要记录dp[i][1]: 最远端在以i为根的子树中的次长长度。

假设best[i]表示：状态dp[i][0]是由状态dp[ best[i] ][0]转移得到，则：

if ( best[i] == fa[i] ) dp[i][2] = max( dp[ fa[i] ][2], dp[ fa[i] ][1] ) + dis[ fa[i] ][i];

else dp[i][2] = max( dp[ fa[i] ][2], dp[ fa[i] ][0] ) + dis[ fa[i] ][i];

因此还需要一次DFS求得dp[i][2], 答案即为max( dp[i][0], dp[i][2] );

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 10010;
 9 
10 struct node
11 {
12     int v;
13     int w;
14     int next;
15 };
16 
17 int N, EdgeN;
18 int head[MAXN];
19 int best[MAXN];
20 int dp[MAXN][3];
21 node D[ MAXN << 1 ];
22 
23 void AddEdge( int u, int v, int w )
24 {
25     D[EdgeN].v = v;
26     D[EdgeN].w = w;
27     D[EdgeN].next = head[u];
28     head[u] = EdgeN++;
29     return;
30 }
31 
32 void DFS1( int u )
33 {
34     for ( int i = head[u]; i != -1; i = D[i].next )
35     {
36         int v = D[i].v;
37         int w = D[i].w;
38         DFS1(v);
39         if ( dp[v][0] + w > dp[u][0] )
40         {
41             dp[u][1] = dp[u][0];
42             dp[u][0] = dp[v][0] + w;
43             best[u] = v;
44         }
45         else if ( dp[v][0] + w > dp[u][1] )
46             dp[u][1] = dp[v][0] + w;
47     }
48     return;
49 }
50 
51 void DFS2( int u )
52 {
53     for ( int i = head[u]; i != -1; i = D[i].next )
54     {
55         int fa = D[i].v;
56         int w = D[i].w;
57         dp[fa][2] = dp[u][2] + w;
58         if ( fa == best[u] )
59             dp[fa][2] = max( dp[fa][2], dp[u][1] + w );
60         else dp[fa][2] = max( dp[fa][2], dp[u][0] + w );
61         DFS2( fa );
62     }
63     return;
64 }
65 
66 int main()
67 {
68     while ( scanf( "%d", &N ) == 1 )
69     {
70         EdgeN = 0;
71         memset( head, -1, sizeof(head) );
72         for ( int v = 2; v <= N; ++v )
73         {
74             int u, w;
75             scanf( "%d%d", &u, &w );
76             AddEdge( u, v, w );
77             AddEdge( v, u, w );
78         }
79 
80         memset( dp, 0, sizeof(dp) );
81         DFS1(1);
82         DFS2(1);
83 
84         for ( int i = 1; i <= N; ++i )
85             printf( "%d
", max( dp[i][0], dp[i][2] ) );
86     }
87     return 0;
88 }