n个城市都在卖一种书，该书的价格在i城市为cost[i]，商人打算从某个城市出发到另一个城市结束，途中可以在任意城市买书或者卖书，但一次只能买一本和卖一本，一个城市到另一个城市需要花费。问商人最大收益是多少。

 

方法一（树形dp）：

　　设dp[u][0]表示在以u为根的树中卖一本书获得的最大价值，dp[u][1]表示在以u为根的树中买一本书获得的最大价值。那么在以u为根的子树中能获得的最大价值为max(dp[u][0])+max(dp[u][1]).

　　

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int MAXN = 1e5 + 100; 8 typedef pair
          
            P; 9 vector
           
 G[MAXN];10 int dp[MAXN][2], ans;11 int cost[MAXN];12 13 void dfs(int u,int pre)14 {15 dp[u][0] = cost[u];16 dp[u][1] = -cost[u];17 for (int i = 0; i < G[u].size(); i++)18 {19 int v = G[u][i].first, w = G[u][i].second;20 if (v == pre) continue;21 dfs(v, u);22 dp[u][0] = max(dp[u][0], dp[v][0] - w);23 dp[u][1] = max(dp[u][1], dp[v][1] - w);24 }25 ans = max(ans, dp[u][0] + dp[u][1]);26 }27 28 int main()29 {30 int T, n,u, v, w;31 scanf("%d", &T);32 while (T--)33 {34 scanf("%d", &n);35 for (int i = 1; i <= n; i++) {36 G[i].clear();37 scanf("%d", &cost[i]);38 }39 for (int i = 1; i < n; i++) {40 scanf("%d%d%d", &u, &v, &w);41 G[u].push_back(P(v, w));42 G[v].push_back(P(u, w));43 }44 ans = 0;45 dfs(1,-1);46 printf("%d\n", ans);47 }48 return 0;49 }