显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int INF=0x7fffffff/2;
typedef long long LL;
const int SIZEN=100010;
int N;
int V[SIZEN]={0};
vector<pair<int,int> > c[SIZEN];
int father[SIZEN]={0};
int ret[SIZEN]={0};
int FD[SIZEN][2]={0};//not return/must return,FD[x][0]>=FD[x][1]
int FU[SIZEN][2]={0};//not return/must return,FU[x][0]>=FU[x][1]
void DFS_down(int x){//from X's father down to X, then down, calc father-edge and X
FD[x][0]=FD[x][1]=V[x];
//if(x==5) cout<<FD[x][0]<<" "<<FD[x][1]<<endl;
int maxdelta=0;
for(int i=0;i<c[x].size();i++){
int u=c[x][i].first,w=c[x][i].second;
if(u==father[x]) continue;
father[u]=x;
DFS_down(u);
int val0=FD[u][0]-w,val1=FD[u][1]-2*w;//take this son
//if(x==3) cout<<u<<" "<<FD[u][0]<<" "<<w<<endl;
val0=max(val0,0),val1=max(val1,0);
FD[u][0]=val0,FD[u][1]=val1;
//cout<<u<<" "<<FD[u][0]<<" "<<FD[u][1]<<endl;
maxdelta=max(maxdelta,val0-val1);
FD[x][1]+=val1;//must return
}
FD[x][0]=FD[x][1]+maxdelta;
//cout<<x<<" "<<FD[5][0]<<endl;
}
void DFS_up(int x){//from X's some son to X, calc father-edge and X, save at sons, not calc son
int ans=V[x];
int mx1=-1,d1=0,mx2=-1,d2=0;
if(father[x]){
ans+=FU[x][1];
int vd=FU[x][0]-FU[x][1];
if(vd>d2){
d2=vd;
mx2=x;
}
if(d2>d1){
swap(d2,d1);
swap(mx2,mx1);
}
}
for(int i=0;i<c[x].size();i++){
int u=c[x][i].first,w=c[x][i].second;
if(u==father[x]) continue;
ans+=FD[u][1];
int vd=FD[u][0]-FD[u][1];
if(vd>d2){
d2=vd;
mx2=u;
}
if(d2>d1){
swap(d2,d1);
swap(mx2,mx1);
}
}
//cout<<"dfsup: "<<x<<" "<<ans<<endl;
ret[x]=ans+d1;
for(int i=0;i<c[x].size();i++){
int u=c[x][i].first,w=c[x][i].second;
if(u==father[x]) continue;
FU[u][1]=ans-FD[u][1]-2*w;
if(u!=mx1) FU[u][0]=FU[u][1]+d1+w;
else FU[u][0]=FU[u][1]+d2+w;
FU[u][0]=max(FU[u][0],0);
FU[u][1]=max(FU[u][1],0);
//cout<<"son: "<<c[x][i].first<<endl;
DFS_up(c[x][i].first);
}
}
void read(void){
scanf("%d",&N);
for(int i=1;i<=N;i++) c[i].clear();
for(int i=1;i<=N;i++) scanf("%d",&V[i]);
int u,v,w;
for(int i=1;i<N;i++){
scanf("%d%d%d",&u,&v,&w);
c[u].push_back(make_pair(v,w));
c[v].push_back(make_pair(u,w));
}
}
int main(){
freopen("excitedtree.in","r",stdin);
freopen("excitedtree.out","w",stdout);
int T=1,kase=0;
//scanf("%d",&T);
while(T--){
read();
father[1]=0;
DFS_down(1);
DFS_up(1);
//printf("Case #%d:\n",++kase);
for(int i=1;i<=N;i++) printf("%d\n",ret[i]);
}
/*cout<<"FD\n";
for(int i=1;i<=N;i++){
cout<<FD[i][0]<<" "<<FD[i][1]<<endl;
}
cout<<"FU\n";
for(int i=1;i<=N;i++){
cout<<FU[i][0]<<" "<<FU[i][1]<<endl;
}*/
return 0;
}
cstdio