题目链接：
http://acm.split.hdu.edu.cn/showproblem.php?pid=5834
Magic boy Bi Luo with his excited tree
Memory Limit: 131072/131072 K (Java/Others)
题意
给你一颗树，每个点有价值，每个边有花费，价值只能取一次，花费每经过一次就要付一次，问从编号为x(x=1,...,n)，能够获得的最大价值是多少。
题解
dp[u][0]:从u往下走能回来的最大价值
dp[u][1]:从u往下走不回来的最大价值（也有可能根本不往下走哦），d[u]:从哪个位置出去不回来的
dp[u][2]:从u往下走不回来的次大价值
这些在第一次dfs的时候就能求出来。令up1表示从父亲出去不回来的最大价值,up2表示从父亲出去要回来的最大价值
那么ans[i]=max(up1+dp[u][0],up2+dp[u][1])
所以在dfs2中维护下up1,up2，就能往下推出所有的ans了。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1e5+10;
int dp[maxn][3],id[maxn];
int val[maxn],ans[maxn];
VPII G[maxn];
//dp[u][0]:从u往下走能回来的最大价值
//dp[u][1]:从u往下走不回来的最大价值（也有可能根本不往下走哦），d[u]:从哪个位置出去不回来的
//dp[u][2]:从u往下走不回来的次大价值
void dfs(int u,int fa) {
dp[u][0]=dp[u][1]=dp[u][2]=val[u];
id[u]=-1;
rep(i,0,G[u].sz()) {
int v=G[u][i].X,w=G[u][i].Y;
if(v==fa) continue;
dfs(v,u);
int tmp=dp[v][0]-2*w;
if(tmp>0) dp[u][0]+=tmp;
}
rep(i,0,G[u].sz()) {
int v=G[u][i].X,w=G[u][i].Y;
if(v==fa) continue;
int tmp=dp[u][0]-max(0,(dp[v][0]-2*w))+max(0,dp[v][1]-w);
if(tmp>dp[u][1]) {
dp[u][2]=dp[u][1];
dp[u][1]=tmp;
id[u]=v;
} else if(tmp>dp[u][2]) {
dp[u][2]=tmp;
}
}
}
//dfs2磨了很久，还是参考别人写出来的：http://www.cnblogs.com/hchlqlz-oj-mrj/p/5774196.html
//当时一直想维护出全局的值，然后就晕了。。xrz
//up1表示从父亲出去不回来的最大价值,up2表示从父亲出去要回来的最大价值
void dfs2(int u,int fa,int up1,int up2) {
ans[u]=max(up1+dp[u][0],up2+dp[u][1]);
rep(i,0,G[u].sz()){
int v=G[u][i].X,w=G[u][i].Y;
if(v==fa) continue;
int dwn2=up2+dp[u][0]-max(0,dp[v][0]-2*w);
dwn2=max(0,dwn2-2*w);
int dwn1=up1+dp[u][0]-max(0,dp[v][0]-2*w);
dwn1=max(0,dwn1-w);
if(id[u]!=v){
int tmp=up2+dp[u][1]-max(0,dp[v][0]-2*w);
tmp=max(0,tmp-w);
dwn1=max(dwn1,tmp);
}else{
int tmp=up2+dp[u][2]-max(0,dp[v][0]-2*w);
tmp=max(0,tmp-w);
dwn1=max(dwn1,tmp);
}
dfs2(v,u,dwn1,dwn2);
}
}
void init(){
rep(i,0,maxn) G[i].clear();
}
int main() {
int tc,kase=0;
int n;
scanf("%d",&tc);
while(tc--) {
scf("%d",&n);
init();
for(int i=1; i<=n; i++) scf("%d",&val[i]);
rep(i,1,n) {
int u,v,w;
scf("%d%d%d",&u,&v,&w);
G[u].pb(mkp(v,w));
G[v].pb(mkp(u,w));
}
dfs(1,-1);
dfs2(1,-1,0,0);
prf("Case #%d:
",++kase);
for(int i=1; i<=n; i++) {
prf("%d
",ans[i]);
}
}
return 0;
}
//end-----------------------------------------------------------------------