树形DP

Shortest Path
https://ac.nowcoder.com/acm/problem/13886

// 第一篇博客有点小紧张
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e4 + 7;
vector<pair<int, int> >    p[N];//记得留个空格在>>处
bool vis[N];
ll dp[N];

void dfs(int u, int fa) {
    int cnt = 0;
    for (int i = 0; i < p[u].size(); ++i) {
        int v = p[u][i].first, w = p[u][i].second;
        if (v == fa)    continue;
        dfs(v, u);
        dp[u] += dp[v];
        if (!vis[v])    dp[u] += w, ++cnt;
    }
    if (cnt & 1)    vis[u] = true;//为奇数u，下一次就配对
    else    vis[u] = false;//未配对子节点为偶数，根节点不参与配对
}

int main() {
    int T = read();
    while (T--) {
        int n = read();
        for (int i = 1; i <= n; ++i)    p[i].clear();//一定要初始化，不然容易死循环
        memset(vis, 0, sizeof(vis));
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n - 1; ++i) {
            int u = read(), v = read(), w = read();
            p[u].push_back(make_pair(v, w));
            p[v].push_back(make_pair(u, w));
        }
        dfs(1, 0);
        printf("%lld\n", dp[1]);
    }
    return 0;
}