题目
Source
http://acm.hdu.edu.cn/showproblem.php?pid=5834
Description
Bi Luo is a magic boy, he also has a migic tree, the tree has N nodes , in each node , there is a treasure, it's value is V[i], and for each edge, there is a cost C[i], which means every time you pass the edge i , you need to pay C[i].
You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times.
Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.
Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?
Input
First line is a positive integer T(T≤104) , represents there are T test cases.
Four each test：
The first line contain an integer N(N≤105).
The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤104).
For the next N−1 lines, each contains three integers u,v,c , which means node u and node v are connected by an edge, it's cost is c(1≤c≤104).
You can assume that the sum of N will not exceed 106.
Output
For the i-th test case , first output Case #i: in a single line , then output N lines , for the i-th line , output ans[i] in a single line.
Sample Input
1
5
4 1 7 7 7
1 2 6
1 3 1
2 4 8
3 5 2
Sample Output
Case #1:
15
10
14
9
15
分析
题目大概说给一棵树，点和边都有权值，经过一点可以加上该点的权值但最多只加一次，经过边会减去该边权值，问从各个点分别出发最多能获得多少权值。
这题是很裸的一种树形DP，做过类似HDU2196就知道怎么做了。两个DFS分别在O(n)处理出两种信息，各个结点往其为根的子树走的信息和各个结点往父亲走的信息，各个结点就能在O(1)合并这两个信息分别得出各个结点的最终信息。。
对于这题需要的状态是：
- dp_down[0/1][u]：u结点往其为根的子树走，并且不走回来/走回来，能得到的最大权值
- dp_up[0/1][u]：u结点往其父亲向上走，并且不走回来/走回来，能得到的最大权值
转移的话，想想就知道了。。dp_up[1][u]可以通过计算各个孩子信息的最大值和次大值求得，其他的比较简单，不过麻烦。。细节要注意，逻辑好考虑清楚。。比赛时我就没考虑好几个逻辑WA了，然后死活找不到错，还好队友A了。。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111111
struct Edge{
int v,w,next;
}edge[MAXN<<1];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
}
int val[MAXN];
int d_down[2][MAXN],d_up[2][MAXN];
void dfs1(int u,int fa){
d_down[0][u]=d_down[1][u]=val[u];
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
dfs1(v,u);
if(d_down[0][v]-2*edge[i].w>0) d_down[0][u]+=d_down[0][v]-2*edge[i].w;
}
int mx=0;
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
if(d_down[0][v]-2*edge[i].w>0){
mx=max(mx,(d_down[1][v]-edge[i].w)-(d_down[0][v]-2*edge[i].w));
}else{
mx=max(mx,d_down[1][v]-edge[i].w);
}
}
d_down[1][u]=d_down[0][u]+mx;
}
void dfs2(int u,int fa){
int mx1=0,mx2=0,tmp;
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
if(d_down[0][v]-2*edge[i].w>0) tmp=(d_down[1][v]-edge[i].w)-(d_down[0][v]-2*edge[i].w);
else tmp=d_down[1][v]-edge[i].w;
if(mx1<tmp){
mx2=mx1;
mx1=tmp;
}else if(mx2<tmp){
mx2=tmp;
}
}
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
int tmp2;
if(d_down[0][v]-2*edge[i].w>0){
tmp2=d_down[0][u]-(d_down[0][v]-2*edge[i].w);
}else{
tmp2=d_down[0][u];
}
int mx=max(d_up[0][u]-2*edge[i].w,tmp2-2*edge[i].w);
mx=max(mx,d_up[0][u]+tmp2-2*edge[i].w-val[u]);
d_up[0][v]=val[v]+max(0,mx);
if(d_down[0][v]-2*edge[i].w>0){
if(mx1==(d_down[1][v]-edge[i].w)-(d_down[0][v]-2*edge[i].w)) tmp=d_down[1][u]-(d_down[1][v]-edge[i].w)+mx2;
else tmp=d_down[1][u]-(d_down[0][v]-2*edge[i].w);
}else if(d_down[1][v]-edge[i].w>0){
if(mx1==d_down[1][v]-edge[i].w) tmp=d_down[1][u]-(d_down[1][v]-edge[i].w)+mx2;
else tmp=d_down[1][u];
}else tmp=d_down[1][u];
mx=max(d_up[1][u]-edge[i].w,tmp-edge[i].w);
mx=max(mx,max(d_up[0][u]+tmp-edge[i].w-val[u],d_up[1][u]+tmp2-edge[i].w-val[u]));
d_up[1][v]=val[v]+max(0,mx);
dfs2(v,u);
}
}
int main(){
int t;
scanf("%d",&t);
for(int cse=1; cse<=t; ++cse){
NE=0;
memset(head,-1,sizeof(head));
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i){
scanf("%d",val+i);
}
int a,b,c;
for(int i=1; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
dfs1(1,1);
d_up[0][1]=d_up[1][1]=val[1];
dfs2(1,1);
printf("Case #%d:
",cse);
for(int i=1; i<=n; ++i){
printf("%d
",max(d_up[0][i]+d_down[1][i],d_up[1][i]+d_down[0][i])-val[i]);
}
}
return 0;
}