Submission #2666736

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct edge{
	int u,v;
	long long w;
	edge(int a,int b,long long c):u(a),v(b),w(c){}
};
long long lazy[N],res[N];
int n,p[N];
vector<vector<int> > sets;
vector<edge> E;
bool cmp(edge &a,edge &b){
	return a.w<b.w;
}
void dsu(int i,int j,long long w){
	for(int k=0;k<sets[i].size();k++){
		res[sets[i][k]]+=lazy[i]-lazy[j]+w*sets[j].size();
		p[sets[i][k]]=j;
	}
	for(int k=0;k<sets[i].size();k++){
		sets[j].push_back(sets[i][k]);
	}
	sets[i].clear();
}
int main(){
	scanf("%d",&n);
	sets.assign(n+1,vector<int>());
	for(int i=1;i<=n;i++){
		p[i]=i;
		sets[i].push_back(i);
	}
	for(int i=1;i<n;i++){
		int u,v;
		long long w;
		cin>>u>>v>>w;
		E.push_back(edge(u,v,w));
	}
	sort(E.begin(),E.end(),cmp);
	reverse(E.begin(),E.end());
	for(int i=0;i<E.size();i++){
		int u=p[E[i].u];
		int v=p[E[i].v];
		int w=E[i].w;
		if(sets[u].size()>sets[v].size()){
			swap(u,v);
		}
		lazy[v]+=w*sets[u].size();
		dsu(u,v,w);
	}
	for(int i=1;i<=n;i++){
		cout<<res[i]+lazy[p[i]]<<"\n";
	}
}

Submission Info

Judge Result