【每日一题】Shortest Path 题解

Solution

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e4 + 5;
const ll mod = 1e8 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct Edge{
  int v, nextz;
  ll w;
}edge[N << 1];
int head[N], tot;
void init(){
  tot = 0;
  memset(head, -1, sizeof(head));
}
void addedge(int u, int v, ll w){
  edge[tot].v = v;
  edge[tot].w = w;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
int sum[N];
ll ans;
void dfs(int u, int par, ll len){
  sum[u] = 1;
  for(int i = head[u]; i != -1; i = edge[i].nextz){
    int v = edge[i].v;
    if(v == par) continue;
    dfs(v, u, edge[i].w);
    sum[u] += sum[v];
  }
  if(sum[u] & 1) ans += len;
}
int main(){
  int t;
  cin >> t;
  while(t--){
    init();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) sum[i] = 0;
    int u, v;
    ll w;
    for(int i = 1; i <= n - 1; i++){
      cin >> u >> v >> w;
      addedge(u, v, w);
      addedge(v, u, w);
    }
    ans = 0;
    dfs(1, -1, 0);
    cout << ans << "\n";
  }
  return 0;
}