【每日一题】Shortest Path

题目链接
思路：显然最坏情况是每个边都被累积了一次。
那么我们考虑怎么样才能使得某些边不被累计到答案里。
很显然，如果一个树边的连接的两个联通分量都是偶数大小的话，说明这条树边不需要被使用就能够将n个点分成n/2组。那么我们直接找到所有的这些边把它的贡献从答案中减去即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,sz[N];
vector<pair<int,int>>v[N];
int s;
LL ans;
void dfs(int x,int y){
  sz[x]=1;
  for(auto k:v[x]){
    if(k.fi==y)
      continue;
    dfs(k.fi,x);
    if(sz[k.fi]%2==0 && (n-sz[k.fi])%2==0)ans-=k.se;
    sz[x]+=sz[k.fi];
  }
}
int main() {
  ios::sync_with_stdio(false);
  int t;
  for(cin>>t;t;t--){
    cin>>n;
    for(int i=1;i<=n;i++)v[i].clear();ans=0;
    for(int i=1;i<n;i++){
      int s,t,w;
      cin>>s>>t>>w;ans+=w;
      v[s].pb({t,w});
      v[t].pb({s,w});
    }
    for(int i=1;i<=n;i++){
      if(v[i].size()==1){
        s=i;
      }
    }
    dfs(s,0);
    cout<<ans<<'\n';
  }
  return 0;
}