點擊打開鏈接

思路：

首先分析一下，我們對每一個邊進行分析，每個邊的左邊有n個節點，右邊有m個節點，那么必然ans+=min(n,m)*邊權

仔細想想，就很清楚，假設左邊節點比右邊少，那么我讓左邊的節點都到右邊去，一定最優。

樹形dp：dp[u]表示包括u節點的子節點個數，對于紅色的那條邊 dp[2]=6, dp[4]=4。取min(4, n-4)*w*2

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+10;vector<pair<int,int> > G[maxn];ll dp[maxn],ans;int a[maxn];struct edge{	int x,y,z;}E[maxn];void dfs(int u){	dp[u] += 1;	for(int i=0; i<G[u].size(); i++){		int v = G[u][i].first;		if(dp[v] == 0){			dfs(v);			dp[u] += dp[v];		}	}}int main(){	int T; cin>>T;	for(int cas=1; cas<=T; cas++){		memset(dp,0,sizeof(dp));		ans = 0;		int n; cin>>n;		for(int i=0; i<=n; i++) G[i].clear();		for(int i=1; i<n; i++){			cin >> E[i].x >> E[i].y >> E[i].z;			G[E[i].x].push_back(make_pair(E[i].y,E[i].z));			G[E[i].y].push_back(make_pair(E[i].x,E[i].z));		}		dfs(1);		for(int i=1; i<n; i++){			int k = min(dp[E[i].x],dp[E[i].y]);			ans += min(k,n-k) * E[i].z * 2;		}		cout << "Case #" << cas << ": " << ans << endl;	}}