【每日一题】Shortest Path

题目大意：
给出N个点，让我们将其分成n/2对，每对点的贡献值为两点距离，求最小距离和。

Solution:
我们可以发现，对于以x为根的子树，若节点个数为奇数，则一定子树中肯定有一个点，要和外边一个点相配对才行，那么对应从父亲到当前节点u这条边就一定会有贡献；若为偶数，则直接在子树中完成配对即可。故dfs维护子树大小，当为奇数时加上根与其父亲节点的边即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll t, tot, n, res, size[N], head[N];

struct Node{
  int to,v,next;
} E[N];

void add(int x, int y, int z) {
  E[tot].to = y;
  E[tot].v = z;
  E[tot].next = head[x];
  head[x] = tot++;
}

void dfs(int now, int val, int pre) {
  size[now] = 1;
  for (int i = head[now]; ~i; i = E[i].next) {
    if (E[i].to == pre) continue;
    dfs(E[i].to, E[i].v, now);
    size[now] += size[E[i].to];
  }
  if (size[now] & 1) res += val;
}

int main() {
  cin >> t;
  while (t--) {
    res = tot = 0;
    memset(head, -1, sizeof(head));
    cin >> n;
    for (int i = 1; i < n; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      add(x, y, z);
      add(y, x, z);
    }
    dfs(1, -1, 0);
    cout << res << '\n';
  }
  return 0;
}