Problem 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
这题没出是我的锅。。有个地方偷个懒少维护个东西结果被卡T了
f[i][0/1]表示这个点为根的情况不返回/返回的最大收益
然后先以1为根做一遍
然后遍历这棵树。手动转换根。每次转换只影响自己和父节点两个
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct line
{
int s,t,x;
int next;
}a[400001];
int head[200001];
int edge;
inline void add(int s,int t,int x)
{
a[edge].next=head[s];
head[s]=edge;
a[edge].s=s;
a[edge].t=t;
a[edge].x=x;
}
int fa[200001],val[200001];
int sx[200001],ans[200001];
int f[200001][2];//0不返回1返回
int fx[200001][2];
inline void dfs(int d)
{
int i,sum=0;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(fa[d]!=t)
{
fa[t]=d;
dfs(t);
if(2*a[i].x<f[t][1])
sum+=f[t][1]-2*a[i].x;
}
}
sx[d]=sum;
int maxx=sum,maxi=0,maxt=0;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(fa[d]!=t)
{
if(2*a[i].x<f[t][1])
{
if(sum-f[t][1]+f[t][0]+a[i].x>maxx)
{
maxt=maxx;
maxx=sum-f[t][1]+f[t][0]+a[i].x;
maxi=t;
}
else if(sum-f[t][1]+f[t][0]+a[i].x>maxt)
maxt=sum-f[t][1]+f[t][0]+a[i].x;
}
else
{
if(sum+f[t][0]-a[i].x>maxx)
{
maxt=maxx;
maxx=sum+f[t][0]-a[i].x;
maxi=t;
}
else if(sum+f[t][0]-a[i].x>maxt)
maxt=sum+f[t][0]-a[i].x;
}
}
}
f[d][0]=maxx+val[d];
f[d][1]=sum+val[d];
fx[d][0]=maxi;
fx[d][1]=maxt+val[d];
}
inline void trdp(int d,int x)
{
int t0=f[fa[d]][0],t1=f[fa[d]][1],ts=sx[fa[d]];
int tt0=f[d][0],tt1=f[d][1],tts=sx[d];
if(2*x<f[d][1])
sx[fa[d]]=sx[fa[d]]+x*2-f[d][1];
int i,sum=sx[fa[d]];
if(fx[fa[d]][0]==d)
{
f[fa[d]][0]=fx[fa[d]][1];
if(f[d][1]>x*2)
f[fa[d]][0]=f[fa[d]][0]-f[d][1]+x*2;
}
else
{
if(f[d][1]>x*2)
f[fa[d]][0]=f[fa[d]][0]-f[d][1]+x*2;
}
f[fa[d]][1]=sum+val[fa[d]];
if(2*x<f[fa[d]][1])
sx[d]=sx[d]-x*2+f[fa[d]][1];
sum=sx[d];
int maxx=sum,maxi=0,maxt=0;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(2*a[i].x<f[t][1])
{
int tt=sum-f[t][1]+f[t][0]+a[i].x;
if(tt>maxx)
{
maxt=maxx;
maxx=tt;
maxi=t;
}
else if(tt>maxt)
maxt=tt;
}
else
{
int tt=sum+f[t][0]-a[i].x;
if(tt>maxx)
{
maxt=maxx;
maxx=tt;
maxi=t;
}
else if(tt>maxt)
maxt=tt;
}
}
f[d][0]=maxx+val[d];
f[d][1]=sum+val[d];
fx[d][0]=maxi;
fx[d][1]=maxt+val[d];
ans[d]=f[d][0];
int dx=fa[d];
fa[dx]=d;
fa[d]=0;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(t!=dx)
trdp(t,a[i].x);
}
f[d][0]=tt0;
f[d][1]=tt1;
f[dx][0]=t0;
f[dx][1]=t1;
fa[d]=dx;
fa[dx]=0;
sx[dx]=ts;
sx[d]=tts;
}
int main()
{
// freopen("1003.in","r",stdin);
// freopen("1003.out","w",stdout);
int T,k=0;
T=read();
while(T>0)
{
T--;
k++;
edge=0;
int n,i,ss,tt,xx;
n=read();
for(i=1;i<=n;i++)
val[i]=read();
for(i=1;i<=n-1;i++)
{
ss=read();tt=read();xx=read();
edge++;
add(ss,tt,xx);
edge++;
add(tt,ss,xx);
}
dfs(1);
ans[1]=f[1][0];
// printf("%d\n",f[1][0]);
for(i=head[1];i!=0;i=a[i].next)
trdp(a[i].t,a[i].x);
printf("Case #%d:\n",k);
for(i=1;i<=n;i++)
printf("%d\n",ans[i]);
for(i=1;i<=n;i++)
{
fa[i]=0;
head[i]=0;
}
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1300081.html
