链接：https://ac.nowcoder.com/acm/problem/13886
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

Today HH becomes a designer, and he faces a problem so he asks you for help.
Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.
HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between the n/2 pairs city is minimum.
Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together.
It's guaranteed that n is even.

输入描述: 

	

		The first line contains an positive integer T(1≤T≤100), represents there are T test cases. 
	


	

		For each test case: The first line contains an positive integer n(1≤n≤104), represents the number of cities in Treeisland, it's guarantee that n is even. 
	


	

		Then n−1 lines followed. Each line contains three positive integer u, v and len, (u≠v,1≤u≤n,1≤v≤n,1≤len≤109)indicating there is a road of length len between u and v. 
	


	

		It's guarantee you can get to any city from any city.

输出描述:

For each test case, output in one line an integer, represent the minimum sum of length.

第一次营业.....

题目大意：

有n个点树，你需要将其每两个一组划分，将其划分为n/2个组，每组的权值定义为两个点之间的距离，求最小距离。

题目思路：


  1. 题目并不难，仔细分析一下即可得知为思维题：可惜我没有仔细分析
  2. 首先考虑特殊情况——叶子节点：叶子节点要选，由于树上的两点路径唯一，那么叶子节点的父边也一定要选。(记住这个一定！)
  3. 对于非叶子节点，考虑子树的个数，如果当前子树有偶数个，那么这偶数个之间绝对两两组合，但是如何两两组合？很简单的例子——菊花图，这时候两两组合就不是你想象中的两两组合。
  4. 菊花中心的点一旦被选必然会有一个点成为奇数点，那么要选这个奇数点，他的父边也一定要选。
  5. 所以由上可以看出：子树大小为奇数的父边一定要选！——联想就算偶数也是两个1组成
  6. 又因为需要贪心求解，所以我们只需要把必须选的边加到答案贡献里就可以了。
  7. 所以这题就变成了，判断一个子树的大小是否为奇数。
    talk is cheap ,show you the code .

    Code: 

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e16;
const int maxn=2e6+6;
const int mod=1000000007;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct dsu{int pre[maxn];void inint(){for(int i=1;i<=n;i++) pre[i]=i;}int Find(int x){return x==pre[x]?x:pre[x]=Find(pre[x]);}void Merge(int x,int y){int dx=Find(x),dy=Find(y);if(dx!=dy) pre[dx]=dy;}};
int pre[maxn];
int sz[maxn];
vector<pair<int,int>>v[maxn];
ll ans=0;
ll dfs(int u,int fa,int w){
    for(auto x:v[u]){
        if(x.first==fa) continue;
        dfs(x.first,u,x.second);
        sz[u]+=sz[x.first];
    }
    if(sz[u]&1) ans+=w;
    return sz[u];
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        read(n);
        ans=0;
        for(int i=1;i<=n;i++) v[i].clear(),sz[i]=1;
        for(int i=1;i<=n-1;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            v[x].push_back({y,z});
            v[y].push_back({x,z});
        }
        dfs(1,1,0);
        printf("%lld\n",ans);
    }
    return 0;
}
/***
2
1 2
0
2
query 1
query 2
***/