Shortest Path

把n个城市分成n/2对，这样n/2对城市之间的长度之和最小。 保证n是均分

样例一：
我们最小的分法是1-2,2-3，答案是5+6=11 其他分法均比这个要大

样例二：

我们选择的是1-3,2-4,5-6 合计5+(3+9)+(10+4)=31

我可以发现，选择2个城市，尽可能要不重复，如果出现交叉重复的，那么不能保证最小了，当某个节点x的子树大小为奇数的时候，我们需要加上节点x和父节点的贡献。在dfs到叶子节点的时候，返回上来，判断下该节点子树大小是不是奇数，是奇数加上其贡献即可。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e4+100;

ll head[N<<1],cnt;
ll t,n;
ll u,v,val;
ll ans;

struct Edge
{
    ll e;
    ll to;
    ll data;
}edge[N<<1];

void add_edge(ll u,ll v,ll val)
{
    cnt++;
    edge[cnt].e=v;
    edge[cnt].to=head[u];
    edge[cnt].data=val;
    head[u]=cnt;
}

ll dfs(ll u,ll f,ll val)
{
    ll ct=1;//当前子树大小 
    for(ll i=head[u];i!=0;i=edge[i].to)
    {
        ll v=edge[i].e;
        ll w=edge[i].data;
        if(v==f)continue;//如果当前节点连接的下一个节点是他的父节点，continue掉 
        ct+=dfs(v,u,w);
    }
    if(ct%2==1)//子树大小是奇数，加上他与父节点的贡献 
    {
        ans+=val; 
    }
    return ct;
}

int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        memset(head,0,sizeof(head));
        ans=0;
        cnt=0;
        scanf("%lld",&n);
        for(ll i=0;i<n-1;i++)
        {
            scanf("%lld%lld%lld",&u,&v,&val);
            add_edge(u,v,val);
            add_edge(v,u,val);
        }
        dfs(1,0,0);
        printf("%lld\n",ans);
    }
    return 0;
}