Submission #2667937

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

struct data{
	int x , y , val;
};
const int N = 1e5 + 1;

int n , pa[N] , ans[N] ,lazy[N];
vector<data> inp;
vector<int> par[N];

bool how_sort(data a , data b){
	return a.val > b.val;
}
signed main(){
	cin >> n;
	pa[n] = n; par[n].pb(n);
	for(int i = 1 ; i < n ; ++ i){
		pa[i] = i ; par[i].pb(i);
		int u , v , w;
		cin >> u >> v >> w;
		inp.pb( data{ u , v , w });
	}	
	sort(inp.begin() , inp.end() , how_sort);
	for(int i = 0 ; i < inp.size() ; ++ i){
		int u = inp[i].x , v = inp[i].y , w = inp[i].val; 
		if(par[pa[u]].size() > par[pa[v]].size()) swap(u,v);
		int z = pa[u];
		lazy[pa[v]] += w * par[z].size();
		int add = w * par[pa[v]].size();
		for(int i = 0 ;i < par[z].size() ; ++ i){
			int k = par[z][i];
			pa[k] = pa[v];
			par[pa[v]].pb(k);
			ans[k] += lazy[z] - lazy[pa[v]] + add;
		}
	}
	for(int i = 0 ;i < par[pa[1]].size() ; ++ i){
		int k = par[pa[1]][i];
		ans[k] += lazy[pa[1]];
	}
	for(int i = 1 ; i <= n ; ++ i)
		cout << ans[i] << "\n";
}

Submission Info

Judge Result