hdu 2196【树形dp】

http://acm.hdu.edu.cn/showproblem.php?pid=2196

题意：找出树中每个节点到其它点的最远距离。

题解：

　　首先这是一棵树，对于节点v来说，它到达其它点的最远距离可以走两个方向，一个是向它的子节点走，不妨称作正向走；一个是向它的父节点方向，不妨称作反向走。也就是说节点v能到达的最远距离是max{正向走的最远距离，反向走的最远距离}。所以可以先dfs一次求出每个节点能正向走的最大距离。显然反向走一定会经过父节点，这时就会出现两种情况：1.父节点u正向走的最远距离经过子节点v。2.父节点u走的最远距离不经过子节点v。当经过子节点v时，显然要算v反向走的最远距离时不能走u的正向最远的那条经过自己的路径，而u的正向第二远的路径将是最优的选择。可以想想看，v反向最远当然是由u的正向最远转移过来的，这个正向最远经不经过v很关键。因此正向dfs时还要记录一个第二最远的距离。

　　设dp[][3],dp[v][0]表示v正向走的最远距离，dp[v][1]表示v正向走的第二最远距离，dp[v][2]表示v反向走的最远距离。

　　那么答案显然是：ans=max{dp[v][0],dp[v][2]}。

　　其中:当u最远不经过v时：dp[v][2]=max{dp[u][2],dp[u][0]}+cost;

　　　　当u最远经过v时：dp[v][2]=max{dp[u][2],dp[u][1]}+cost;

　　我之前有个非常疑惑的地方就是为什么dp[v][2]的转移还要有dp[u][2]？我直接根据u经不经过v分两种情况不就是dp[v][2]了吗，怎么还要跟dp[u][2]+cost之间取个最大值？后来想想才明白，其实这也是个状态转移啊！dp[u][2]表示u反向走的最远距离，而dp[u][0],dp[u][1]都是正向走的距离，当由u推v的时候当然要从u的正向和反向之间取个最大值了！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=10007;
 8 struct Node{
 9     int to,cost;
10 };
11 vector<Node> tree[MAXN];
12 int dp[MAXN][3];
13 int N;
14 
15 void init()
16 {
17     memset(dp,0,sizeof(dp));
18     for(int i=0;i<=N;i++)
19         tree[i].clear();
20 }
21 
22 void dfs1(int u,int fa)
23 {
24     int FirstMax=0,SecondMax=0;
25     for(int i=0;i<tree[u].size();i++){
26         int v=tree[u][i].to;
27         int c=tree[u][i].cost;
28         if(v==fa) continue;
29         dfs1(v,u);
30         if(dp[v][0]+c>FirstMax){
31             SecondMax=FirstMax;
32             FirstMax=dp[v][0]+c;
33         }else if(dp[v][0]+c>SecondMax)
34             SecondMax=dp[v][0]+c;
35     }
36     dp[u][0]=FirstMax;
37     dp[u][1]=SecondMax;
38 }
39 
40 void dfs2(int u,int fa)
41 {
42     int t;
43     for(int i=0;i<tree[u].size();i++){
44         int v=tree[u][i].to;
45         int c=tree[u][i].cost;
46         if(v==fa) continue;
47         if(dp[u][0]==dp[v][0]+c)
48             t=dp[u][1];
49         else t=dp[u][0];
50         dp[v][2]=max(dp[u][2],t)+c;
51         dfs2(v,u);
52     }
53 }
54 
55 int main()
56 {
57     while(scanf("%d",&N)==1)
58     {
59         init();
60         int a,b;
61         Node n1;
62         for(int i=2;i<=N;i++){
63             scanf("%d%d",&a,&b);
64             n1.to=a,n1.cost=b;
65             tree[i].push_back(n1);
66             n1.to=i;
67             tree[a].push_back(n1);
68         }
69         dfs1(1,1);
70         dfs2(1,1);
71         for(int i=1;i<=N;i++)
72             printf("%d
",max(dp[i][0],dp[i][2]));
73     }
74     return 0;
75 }