这题咋一看以为是图论题 在看n个点与n-1条边那就是树了 题目要分成两边后边权最小
首先我们分析是平均分 那么一棵树的子树（包括他自己）是奇数的话 一定有一个点被分给另一边
然后再结合样例手动推到 当一颗树的子树是奇数那么他父亲节点的边权值一定会被用到
于是程序就出来了 统计子树节点 判断是否为奇数 然后决定是否加入答案
代码有详细注释

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define inf 1e18
ll const maxn=2e5+10;
struct M{///链式前向星存图
    ll to,next,val;///终点，同起点的上一条边的编号，边权
}edge[maxn<<1];///边集
ll n,t,u,v,w,cnt,head[maxn],ans;
void add(ll u,ll v,ll w)
{
  edge[++cnt].next = head[u];///以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
  edge[cnt].to=v;///终点
  edge[cnt].val=w;///权值
  head[u]=cnt;///更新以u为起点上一条边的编号
}
ll dfs(ll u,ll fa,ll s)
{
    ll ant=1;
    for(int i=head[u];i!=0;i=edge[i].next)///遍历记录子树个数
    if(edge[i].to!=fa)   ant+=dfs(edge[i].to,u,edge[i].val);
    if(ant%2==1)   ans+=s;///答案
    return ant;
}
int main() {
  scanf("%lld",&t);
  while(t--)
  {
    memset(head,0,sizeof(head));cnt=0,ans=0;///了解存储原理  每次只需要更新head和cnt
    scanf("%lld",&n);
    for(ll i=1;i<=n-1;++i)
    {
    scanf("%d%d%d",&u,&v,&w);///u,v节点 w权值
    add(u,v,w);
    add(v,u,w);
    }
    dfs(1,0,0);
    cout<<ans<<endl;
  }
  return 0;
}