换根dp

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=1e5+5;
vector<pll> g[N];
int n;
ll f[N],tt[N];//tt[i]表示父亲对子树的贡献
//f[i]表示以1为根节点，以i为子树根节点，能流下的最大值 
void up(int u,int father)
{
    int ge=0;
    for(auto pp:g[u])
    {
        ll v=pp.first,w=pp.second;
        if(v==father)continue;
        up(v,u);
        ge++;
        f[u]+=min(w,f[v]);
    }
    if(ge==0)f[u]=9e18;
}
void down(int u,int father)
{
    for(auto pp:g[u])
    {
        ll v=pp.first,w=pp.second;
        if(v==father)continue;
        if(f[u]-min(f[v],w)+tt[u]==0)
        tt[v]=w;
        else //为0，则为边权 
        tt[v]=min(w,f[u]-min(f[v],w)+tt[u]);
        down(v,u);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    up(1,-1);
    down(1,-1);
    for(int i=1;i<=n;i++)
    {
        if(f[i]==9e18)
        cout<<tt[i]<<endl;
        else cout<<f[i]+tt[i]<<endl;
    }
    return 0;
 }