ABC409E

ABC409E

解法

下限を求める事と，求めた下限を実現出来ることを示す．

辺に注目する．辺で木を2つの連結成分に分断すれば，独立な2つの木になる．
一つの頂点に集めるとき，その辺を必ず通らないといけない．
根が指定されてないので，辺を通る向きは不明．

main

int main() {
	ll n;
	cin >> n;
	vll a(n); rep(i,n) { cin >> a[i]; }

	vector<vector<pll>> g(n);
	rep(i,n-1){
		ll a,b,c; cin >> a >> b >> c;
		--a, --b;
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}

	ll ans = 0;
	auto dfs = [&](auto dfs, ll cv, ll pv) -> void {
		for(auto [nv, cost]: g[cv]) if(nv != pv){
			dfs(dfs, nv, cv);
			
			// rem: 戻るときに計上
			a[cv] += a[nv];
			ans += abs(a[nv]) * cost; // rem: abs
		}
	};

	dfs(dfs, 0, -1);
	cout << ans << endl;
	
	return 0;
}