NC13886

題意

給你一顆n(偶數(shù)）結(jié)點(diǎn)的樹，將其分為n/2對(duì)，求所有對(duì)數(shù)相連的路徑之和最小為多少？

思路

DFS 數(shù)據(jù)結(jié)構(gòu)
既然是圖論那就先畫圖吧
左圖由于以2號(hào)結(jié)點(diǎn)為根節(jié)點(diǎn)的子樹結(jié)點(diǎn)數(shù)(包括其自身)為3（奇數(shù)），那么顯然這棵樹上一定有個(gè)節(jié)點(diǎn)要從樹外找一個(gè)節(jié)點(diǎn)相連，那么必須要經(jīng)過2號(hào)結(jié)點(diǎn)與其父節(jié)點(diǎn)的這條路(2->1)。
右圖告訴我們?nèi)绻芘紨?shù)配對(duì)的子樹則不需要相連。
葉子節(jié)點(diǎn)為子樹的結(jié)點(diǎn)數(shù)一定為1顯然一定會(huì)加上。
DFS求子樹的結(jié)點(diǎn)數(shù)，若結(jié)點(diǎn)數(shù)為奇數(shù)則需要該節(jié)點(diǎn)與其父節(jié)點(diǎn)相連的這一條邊，若為偶數(shù)則不需要。

注意：多組數(shù)據(jù)要每次清空vector數(shù)組，然后置于cnt數(shù)組不需要memset是因?yàn)閐fs里面一開始都會(huì)賦過1，所以無影響。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e4 + 5;

ll res,n,cnt[N];
vector<P> G[N];

void dfs(ll u,ll fa,ll cost){
	cnt[u]=1;
	for(auto c:G[u]){
		ll x=c.fi,y=c.se;
		if(x==fa) continue;//若為父節(jié)點(diǎn)當(dāng)然不做啦
		dfs(x,u,y);//遞歸求子樹的節(jié)點(diǎn)數(shù)量
		cnt[u]+=cnt[x];
	}
	if(cnt[u]&1) res+=cost;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n;int t=n-1;res=0;
		for(int i=1;i<=n;i++) G[i].clear();
		while(t--){
			ll u,v,w;
			cin>>u>>v>>w;
			G[u].push_back(P(v,w));
			G[v].push_back(P(u,w));
		}
		dfs(1,-1,0);
		cout<<res<<'\n';
	}
	return 0;
}