题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5834
题目大意：
一棵N个点的有根树，每个节点有价值ci，每条树边有费用di,节点的值只能取一次，边权每次经过都要扣，问从每一个节点开始走最大能获得的价值。
题目思路：
【树形动态规划】
首先用dfs求出从根1往下走的：节点u往下走最后回到节点u的最大值g[u]，节点u往下走最后不回到u的最优值和次优值f[0][u],f[1][u]
接着考虑一个节点u，除了以上的情况还有可能是往它的父亲方向走，这里就分两种，一种是走父亲那边再回来走自己的子树，还有一种是走自己的子树再回来走父亲那边
(肯定最后都不会特意回到u，因为边权>0，回到自己不会更优)而这些状态都可以通过dfs里求得f和g推出。
具体推法我已写在代码注释中，希望没有写错。。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 100004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
int w[N],last[N],g[N];
int f[][N],from[][N],h[][N];
struct xxx
{
int next,to,d;
}a[N+N];
bool mark[N];
void add(int x,int y,int z)
{
a[++lll].d=z;
a[lll].to=y;
a[lll].next=last[x];
last[x]=lll;
}
void dfs(int u,int fa)//从根开始往下走的解
{
int i,j,v;
g[u]=w[u];
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
if(v==fa)continue;
dfs(v,u);
g[u]+=max(,g[v]-a[i].d-a[i].d);//g[u]统计最后回到u的最优解
}
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
if(v==fa || f[][v]<=a[i].d)continue;
j=g[u]-max(,g[v]-a[i].d-a[i].d)+max(,f[][v]-a[i].d);
//枚举从u哪一条走下去不回，如果g[u]计算时有走v则要扣掉，再加上选择走v不回的最优值
if(f[][u]<=j)//不回u的最优值
{
f[][u]=f[][u],from[][u]=from[][u];
f[][u]=j,from[][u]=i;
}
else if(f[][u]<j)//不回u的次优值
f[][u]=j,from[][u]=i;
}
f[][u]=max(f[][u],g[u]);
f[][u]=max(f[][u],g[u]);
}
void work(int u,int fa)//计算最后答案
{
int i,j,v;
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
if(v==fa)return;
j=max(,g[v]-a[i].d-a[i].d);//u走到v再走回来是否更优
h[][v]=f[][v]+max(,g[u]-j-a[i].d-a[i].d);//g[u]扣除掉走v子树的值，先从v向上走到u再从u走回来，然后走回v的最优值
h[][v]=f[][v]+max(,g[u]-j-a[i].d-a[i].d);//次优值
from[][v]=i;
if(g[v]>=a[i].d+a[i].d)//这种情况下前面多扣了一次边权
{
if(from[][u]!=i)h[][v]=h[][u]+a[i].d;//v往上走回头再往下走不回头
else h[][v]=h[][u]+a[i].d;//当前是最优值，选另一条走次优值
}
else//前面少扣了一次边权
{
if(from[][u]!=i)h[][v]=h[][u]+g[v]-a[i].d;//v往下走回头再往上走不回头
else h[][v]=h[][u]+g[v]-a[i].d;
}
if(h[][v]>h[][v])swap(h[][v],h[][v]),swap(from[][v],from[][v]);
if(h[][v]>h[][v])swap(h[][v],h[][v]),swap(from[][v],from[][v]);
g[v]+=max(,g[u]-j-a[i].d-a[i].d);//更新答案
work(v,u);
}
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z;
// for(scanf("%d",&cass);cass;cass--)
for(scanf("%d",&cas),cass=;cass<=cas;cass++)
// while(~scanf("%s",s+1))
// while(~scanf("%d",&n))
{
mem(f,);mem(from,);mem(last,);lll=;
printf("Case #%d:\n",cass);
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&w[i]);
for(i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(,);
h[][]=f[][],h[][]=f[][];
work(,);
for(i=;i<=n;i++)
printf("%d\n",h[][i]);
}
return ;
}
/*
// //
*/