http://acm.hdu.edu.cn/showproblem.php?pid=6201
n个城市都在卖一种书,该书的价格在i城市为cost[i],商人打算从某个城市出发到另一个城市结束,途中可以在任意城市买书或者卖书,但一次只能买一本和卖一本,一个城市到另一个城市需要花费。问商人最大收益是多少。
方法一(树形dp):
设dp[u][0]表示在以u为根的树中卖一本书获得的最大价值,dp[u][1]表示在以u为根的树中买一本书获得的最大价值。那么在以u为根的子树中能获得的最大价值为max(dp[u][0])+max(dp[u][1]).
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 1e5 + ;
typedef pair<int, int> P;
vector<P> G[MAXN];
int dp[MAXN][], ans;
int cost[MAXN]; void dfs(int u,int pre)
{
dp[u][] = cost[u];
dp[u][] = -cost[u];
for (int i = ; i < G[u].size(); i++)
{
int v = G[u][i].first, w = G[u][i].second;
if (v == pre) continue;
dfs(v, u);
dp[u][] = max(dp[u][], dp[v][] - w);
dp[u][] = max(dp[u][], dp[v][] - w);
}
ans = max(ans, dp[u][] + dp[u][]);
} int main()
{
int T, n,u, v, w;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = ; i <= n; i++) {
G[i].clear();
scanf("%d", &cost[i]);
}
for (int i = ; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(P(v, w));
G[v].push_back(P(u, w));
}
ans = ;
dfs(,-);
printf("%d\n", ans);
}
return ;
}