题解：AT_abc222_f [ABC222F] Expensive Expense

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+100;
int n,b[N];
struct edge{int t,w;};vector<edge> a[N];
int d[N];
int dfn[N],udfn[N],ls[N],tot;
void dfs2(int x,int fa)
{
	dfn[x]=ls[x]=++tot;
	udfn[dfn[x]]=x;
	for(auto i:a[x])
	{
		if(i.t==fa)continue;
		dfs2(i.t,x);
	}
	ls[x]=tot;
}
void dfs(int x,int fa)
{
	for(auto i:a[x])
	{
		if(i.t==fa)continue;
		d[i.t]=d[x]+i.w;
		dfs(i.t,x);
	}
}
namespace sg
{
	struct node
	{
		int add,mx;
	}t[N*4];
	#define ll (x<<1)
	#define rr (x<<1|1)
	#define xx (t[x])
	#define mid ((l+r)>>1)
	void build(int x,int l,int r)
	{
		if(l==r){xx.mx=d[udfn[l]];return;}
		build(ll,l,mid);
		build(rr,mid+1,r);
		xx.mx=max(t[ll].mx,t[rr].mx);
	}
	inline void add(int l1,int r1,int l,int r,int x,int val)
	{
		if(l>=l1&&r<=r1){xx.add+=val,xx.mx+=val;return;}
		if(l1<=mid)add(l1,r1,l,mid,ll,val);
		if(r1>mid)add(l1,r1,mid+1,r,rr,val);
		xx.mx=max(t[ll].mx,t[rr].mx)+xx.add;
	}
	inline int get(int pos,int l,int r,int x)
	{
		if(l==r)return t[x].mx;
		if(pos<=mid)return get(pos,l,mid,ll)+xx.add;
		else return get(pos,mid+1,r,rr)+xx.add;
	}
	#undef ll
	#undef rr
	#undef xx
	#undef mid
}
using namespace sg;
int ans[N];
void dfs1(int x,int fa)
{
	add(dfn[x],dfn[x],1,n,1,-b[x]);
	// assert(get(dfn[x],1,n,1)==0);
	ans[x]=t[1].mx;
	add(dfn[x],dfn[x],1,n,1,b[x]);
	for(auto i:a[x])
	{
		if(i.t==fa)continue;
		add(dfn[i.t],ls[i.t],1,n,1,-i.w);
		if(dfn[i.t]!=1)add(1,dfn[i.t]-1,1,n,1,i.w);
		if(ls[i.t]!=n)add(ls[i.t]+1,n,1,n,1,i.w);
		dfs1(i.t,x);
		add(dfn[i.t],ls[i.t],1,n,1,i.w);
		if(dfn[i.t]!=1)add(1,dfn[i.t]-1,1,n,1,-i.w);
		if(ls[i.t]!=n)add(ls[i.t]+1,n,1,n,1,-i.w);
	}
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	int x,y,z;
	for(int i=1;i<n;i++){cin>>x>>y>>z;a[x].push_back({y,z});a[y].push_back({x,z});}
	for(int i=1;i<=n;i++)cin>>b[i];
	dfs2(1,0);
	dfs(1,0);
	for(int i=1;i<=n;i++)d[i]+=b[i];
	build(1,1,n);
	dfs1(1,0);
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}