每日一题4月3日

题意：给你一棵 n个节点的树（保证 n 是偶数），你需要将 n 个节点分为 n/2 个点对，使得每个点对的两个点的距离的和最小。
思路：我们可以发现若以u为根的子树节点个数为奇数那么无法在子树内进行匹配，会有一个节点对外匹配，所以标记一下节点数在加上每次对外匹配的值即可

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
const int MAX =2e5+20;
const double PI = 3.14159265359;

//const int mod = 1e9 + 7;
struct node{
  int to,nex,val;
}edge[MAX*2];
int n,m,s, cnt=0,head[MAX*2];

void add(ll u,ll v,ll w)
{
    cnt++;
    edge[cnt].to=head[u];
    edge[cnt].val=w;
    edge[cnt].nex=v;
    head[u]=cnt;
}
int vis[MAX*2];
ll ans=0;
void dfs(ll u,ll fa,ll w)
{
     vis[u]=1;
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        if(edge[i].nex!=fa){
            dfs(edge[i].nex,u,edge[i].val);
            vis[u]+=vis[edge[i].nex];
        }
    }
    if(vis[u]%2==1) ans+=w ;
}
int main()
{
    SIS;
    int t;
    cin>>t;
    while(t--)
    {
         ll u,v,w;
         cin>>m;
    for(int i=0;i<m-1;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);


    }
    dfs(1,0,0);
    cout<<ans<<endl;
    ans=0;
    cnt=0;
   memset(head,0,sizeof(head));
   memset(vis,0,sizeof(vis));

    }

    return 0;

}