HDU 5834 Magic boy Bi Luo with his excited tree

题目：Magic boy Bi Luo with his excited tree

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5834

题意：给一棵树，在树的每个结点可以收获一定的积分，每一条边会消耗一定的积分，每个结点积分取一次便完，但每次路过一条边，都会消耗积分，问从每一个结点出发，最多能捞多少积分。N范围10万，样例数1万。

思路：

　　不难的一道题，但细节较多，容易出错。

　　树形DP。

　　从i 点出发，大致可以分为向上和向下两种，先考虑向下的情况。可以想到，假设i 连着n 条边，那么如果要想把n 条边外的积分都拿到手，那么n 条边，有n-1 条边要走两次。那么，我们可以设置dp 如下：

　　dp[i]：从i 出发，又回到i 的最优解

　　fen[i][0]：从i 出发，不回到i 的最优解 ----- fen[i][1]：最终朝着哪个边离开

　　fen[i][2]：从i 出发，不回到i 的次优解

　　对i 结点，我们需要的信息就是上面4 个，一次dfs可以求出。

　　对根节点rt，他的答案ans[rt] = fen[rt][0]。对于中间的某个结点x，ans[x] 是两种情况取最大，一：从i 出发，往上方走，又回到i ，再往下方走（不回来了），其中往下方走不回来就是fen[x][0]，往上方走又回来（暂放）。二：从i 出发，往下方走，又回到i ，再往上方走（不回来），这里往下方走又回来就是dp[x]，往上方走不会来（暂放）。

　　上面这一步中dfs要传两个参数（up1，up2），up1表示往上方走不回来的最优解，up2表示往上方走又回来的最优解。现在我们来解决这两个参数，在x 点时，对于x 的某个孩子son ，e是x 和son 连接的边，假如这个son 就是fen[x][1]，那么fen[x][2]-max(0,dp[son]-2*e)就代表了从x 出发，不往son 方向走又不回来的最优解，如果son 不是fen[x][1]，那么这个最优解就是fen[x][0]-max(0,dp[son]-2*e)，而up1代表了从x 出发，往上方走，不回来的最优解，那么要想两者都得到，要么往上方走回来（up2），要么往下方走回来（dp[x]-max(0,dp[son]-2*e)），这两个可以取最优解，就可以得到son 的up1、up2参数（up1要减去e，up2要减去2e）。

提供一组数据：

2
5
1 2 2 2 2
1 2 1
1 3 1
3 4 3
3 5 3
7
1 4 1 7 6 9 8
1 2 2
1 3 1
2 4 3
2 5 4
3 6 6
3 7 7

答案为：

1. 2 3 3 2 2

2. 7 8 7 10 10 10 8

我在倒二个10 弄了半天，一直显示9 ，搞了半天

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 #define N 100010
 7 vector<pair<int,int> > v[N];
 8 int w[N];   //w[i] : 点i 的权值
 9 int dp[N];  //dp[i] : 从i 往下走，又回到i 的最大收获
10 int fen[N][3];
11 /*
12   fen[i][0] : 从i 出发，不回到i 的最大收获
13   fen[i][1] : 从i 出发，不回到i 的最大收获 的 最后路径（就是不重复两次的那条）
14   fen[i][2] : 从i 出发，不回到i 的次大收获
15 */
16 void dfs(int rt,int fa)
17 {
18   dp[rt]=w[rt];
19   for(int i=0;i<v[rt].size();i++)
20   {
21     if(v[rt][i].first==fa) continue;
22     dfs(v[rt][i].first,rt);
23     dp[rt] += max(0 , dp[v[rt][i].first] - 2*v[rt][i].second);
24   }
25   fen[rt][1]=-1;
26   fen[rt][0]=fen[rt][2]=w[rt];
27   for(int i=0;i<v[rt].size();i++)
28   {
29     int ad=v[rt][i].first;
30     int wa=v[rt][i].second;
31     if(ad==fa) continue;
32     int now = dp[rt] - max(0 , dp[ad]-2*wa) + max(0 , fen[ad][0]-wa);
33     // now 就是从这条路径出发不回来的收获
34     if(now>fen[rt][0])
35     {
36       fen[rt][2]=fen[rt][0];
37       fen[rt][0]=now;
38       fen[rt][1]=i;
39     }
40     else if(now>fen[rt][2]) fen[rt][2]=now;
41   }
42 }
43 int ans[N];
44 void dfs2(int rt,int fa,int up1,int up2)
45 {//up1 : rt父结点出去不回来的最优解 up2 : rt父结点出去又回到父结点的最优解
46   ans[rt]=max(dp[rt]+up1,up2+fen[rt][0]);
47 
48   for(int i=0;i<v[rt].size();i++)
49   {
50     int ad=v[rt][i].first;
51     int wa=v[rt][i].second;
52     if(ad==fa) continue;
53     int down1,down2;
54     if(fen[rt][1]==i) down1=max(0 , fen[rt][2] - max(0,dp[ad]-2*wa));
55     else down1=max(0 , fen[rt][0] - max(0,dp[ad]-2*wa));
56     down2=max(0 , dp[rt] - max(0,dp[ad]-2*wa));
57     down1=max(0 , max(up1+down2-wa,up2+down1-wa));
58     down2=max(0 , up2+down2-2*wa);
59     dfs2(ad,rt,down1,down2);
60   }
61 }
62 int main()
63 {
64   int t,n,x,y,z,cas=1;
65   scanf("%d",&t);
66   while(t--)
67   {
68     scanf("%d",&n);
69     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
70     for(int i=1;i<n;i++)
71     {
72       scanf("%d%d%d",&x,&y,&z);
73       v[x].push_back(make_pair(y,z));
74       v[y].push_back(make_pair(x,z));
75     }
76     dfs(1,0);
77     dfs2(1,0,0,0);
78     printf("Case #%d:
",cas++);
79     for(int i=1;i<=n;i++) printf("%d
",ans[i]);
80     for(int i=1;i<=n;i++) v[i].clear();
81   }
82   return 0;
83 }