Take root of the tree as 1. Precalculate the number of children of each node.

1. Calculate answer for the root.

2. Now do a dfs traversal. Suppose x is the current node and y is the node to which we will go. Let e be the edge weight and child[y] represent the number of children of y.

The paths till y will have their weights decremented by e (there will be a total of child[y] such paths)

The paths till x will have their weights incremented by e (there will be a total of n-child[y] such paths)

#include<bits/stdc++.h>
#define rep(i,start,lim) for(lld i=start;i<lim;i++)
#define repd(i,start,lim) for(lld i=start;i>=lim;i--)
#define scan(x) scanf("%lld",&x)
#define print(x) printf("%lld ",x)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define br printf("\n")
#define sz(a) lld((a).size())
#define YES printf("YES\n")
#define NO printf("NO\n")
#define all(c) (c).begin(),(c).end()
using namespace std;
#define INF         1011111111
#define LLINF       1000111000111000111LL
#define EPS         (double)1e-10
#define MOD         1000000007
#define PI          3.14159265358979323
using namespace std;
typedef long double ldb;
typedef long long lld;
lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
typedef vector<lld> vlld;
typedef pair<lld,lld> plld;
typedef map<lld,lld> mlld;
typedef set<lld> slld;
#define N 100005
vector<plld> adj[N];
lld n,sons[N],ans[N],cnt;
void dfs1(lld curr,lld par)
{
	sons[curr]=1;
	for(auto i:adj[curr])
		if(i.f!=par)
			dfs1(i.f,curr),sons[curr]+=sons[i.f];
}
void dfs2(lld curr,lld par,lld dis)
{
	for(auto i:adj[curr])
		if(i.f!=par)
			cnt+=(i.s+dis),dfs2(i.f,curr,i.s+dis);
}
void dfs3(lld curr,lld par,lld dis)
{
	for(auto i:adj[curr])
		if(i.f!=par)
			ans[i.f]=dis+(i.s * (n-2*sons[i.f])),dfs3(i.f,curr,ans[i.f]);
}
int main()
{
	lld t,x,y,z;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cnt=0;
		rep(i,0,n-1)
		{
			cin>>x>>y>>z;
			adj[x].pb({y,z});
			adj[y].pb({x,z});
		}
		dfs1(1,0);
		dfs2(1,0,0);
		ans[1]=cnt;
		dfs3(1,0,cnt);
		rep(i,1,n+1) cout<<ans[i]<<" ";br;
		rep(i,0,N) adj[i].clear();
	}
	return 0;
}

It is actually very similar to COCI 2016/2017 CONTEST #6 P5. You can build the mst only with n log n edges. First merge i and j for zero cost if a[i] % a[j] = 0, then for every distinct a[i], add edge between i and j with cost a[j] % a[i], if a[j] > a[i] * p, where p >= 0 and there isn't exist a[k] s.t. a[i] < a[k] < a[j], i.e. a[j] is the first number in a that strictly larger than a[i] * p. Total cost of the mst is the answer.

Hi,

well — not sure, whether it is correct (I hope so) but here's our approach.

Two facts:

A) You can use every node ([x,y]) just once

B) The grind (under dominoes) is Bipartite Graph

Well, from these fact one shall consider Matching :) Anyway:

I) The matching is not maximal (just matching up to K)

II) You are not interested in matching itself (it will in most cases be K) but for some value of it (you want maximal such value) => So we want matching with cost :)

So what now — Let us consider following matching (capacity/cost):

(Source1) → K/0 → Source2 →→→ 1/0 →→→ WhiteSquare →→1/INF-CostA-CostB →→ BlackSquare →→ 1/0 →→ Sink

If you execute this matching [Min Cost Max Flow], and subtract it from "flow*INF", you will get the sum of squares you won't consider — so subtracting this value from sum of all squares will get the right answer.

Well you might see a problem here: The size of parity is ~4.5*10^6 which is NOT sufficient for bipartite matching. But if you give it a small observation, you'll see, that there is no reason to consider ALL pairs of adjacent squares. Well if we consider optimal solution, it would be somewhere BETWEEN those pairs with the biggest sum of values.

Off-course the most valued pairs might overlap, and it might lead to iniquity, so we shall find the bound of "enough" points (well or we can pick a VERY BIG VALUE {which is enough for mcmf}).

SO: Get input → process all edges → sort edges be sizes → create reduced bipartite graph → do MCMF-algo → $$ Profit

Good Luck & Have Nice Day!