Submission #2666904

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int,int> ii;

typedef pair<int,ii> iii;

int n,par[100005];
long long lz[100005];
vector<iii> edge;
long long ans[100005];
vector<int> st[100005];

int findSet(int u){
    if(u == par[u]) return u;
    return par[u] = findSet(par[u]);
}
void UnionSet(int u,int v,int val){
    int pu = findSet(u), pv = findSet(v);
    if(st[pu].size()>st[pv].size()) swap(pu,pv);
    for(int i = 0;i<st[pu].size();i++){
        ans[st[pu][i]]+=val*st[pv].size();
        ans[st[pu][i]]+=lz[pu];
        ans[st[pu][i]]-=val*st[pu].size();
        ans[st[pu][i]]-=lz[pv];
    }
    lz[pu] = 0;
    for(int i = 0;i<st[pu].size();i++)
        st[pv].pb(st[pu][i]);
    lz[pv]+=val*st[pu].size();
    par[pu] = pv;
}

int main(){
    cin.tie(0),ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1;i<=n;i++){
        par[i] = i;
        st[i].pb(i);
    }
    int u,v,w;
    for(int i = 1;i<=n-1;i++){
        cin >> u >> v >> w;
        edge.pb(mp(w,mp(u,v)));
    }
    sort(edge.begin(),edge.end());
    for(int i = edge.size()-1;i>=0;i--){
        u = edge[i].se.fi; v = edge[i].se.se;
        w = edge[i].fi;
        UnionSet(u,v,w);
    }
    for(int i = 1;i<=n;i++)
        cout<<ans[i]+lz[findSet(i)]<<"\n";
}

Submission Info

Judge Result