hdu4118

枚举每条边最多被经过的次数即可

 

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=100005;
typedef long long ll;
struct e{
	int v, len;
	e* nxt;
}es[N<<1], *fir[N];
int n, en;
int que[N], par[N], size[N], lens[N];
void add_e(int u, int v, int len){
	es[en].v=v;
	es[en].len=len;
	es[en].nxt=fir[u];
	fir[u]=&es[en++];
}
void insert(int u, int v, int len){
	add_e(u, v, len);
	add_e(v, u, len);
}
bool input(){
	scanf("%d", &n);
	int i, u, v, len;
	for(i=1; i<=n; i++){
		fir[i]=NULL;
	}
	en=0;
	for(i=1; i<n; i++){
		scanf("%d%d%d", &u, &v, &len);
		insert(u, v, len);
	}
	return true;
}
int ca=0;
void solve(){
	int l, r, u, v, i;
	e* cur;
	ll ans;
	for(l=r=0, par[1]=-1, lens[0]=0, que[r++]=1; l!=r; ){
		for(cur=fir[u=que[l++]]; cur; cur=cur->nxt){
			if((v=cur->v)!=par[u]){
				par[v]=u;
				que[r++]=v;
				lens[v]=cur->len;
			}
		}
	}
	for(ans=0, i=n-1; i>=0; i--){
		size[u=que[i]]=1;
		for(cur=fir[u]; cur; cur=cur->nxt){
			if((v=cur->v)!=par[u]){
				size[u]+=size[v];
			}
		}
		ans += (ll)min(size[u], n-size[u])*lens[u]*2;
	}
	printf("Case #%d: %I64d\n", ++ca, ans);
}
int main(){
	

	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}