题解：AT_abc222_f [ABC222F] Expensive Expense

题面要求求每个点的答案，考虑换根。因为有 d 数组的限制，每次维护所有点与当前点的距离。每次换根时子树内的点距离减 1，子树外的点距离加 1，可以转化为 dfn 序上最多 3 个区间的区间加，同时维护最大值，用线段树实现。换回根时减去相应贡献即可。注意统计最长距离时不要算上自己，虽然不知道数据中有没有这样的点。

代码。

#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';
}