Shortest Path

感受
题目出得很好，但是我觉得题解讲得不是太好，也有可能是我太菜了。
弄懂这题，我看的是cf官方题解E题https://codeforces.ml/blog/entry/72212
思路
我自己也YY一下，其实这是一道考虑边权对答案的贡献题。
我们考虑某一个树边，树边W上有两个端点，记为u和v
那么考虑任意一种配对方式，如果树边W被多余1对的最短路经过，假设经过W的最短路有

1. 
2. 
   那我们可以贪心减少费用，把这路径进行转化（假设a1与a3在u的左侧，a2与a4在v的右侧）
3. 
4. 
   在保证路径的前提下，只删除了u-v
   可能讲得比较突兀，我上一下CF官方题解的图
   

然后，我们只需要考虑每条边对答案是否有贡献即可，后面比较简单，我就不YY了。不会可以自己思考或者看那个官方题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
int dp[maxn];///dp[i]表示以i为根的树大小
struct edge{
    int v, nex; ll w;
}e[maxn * 2];
int head[maxn], n, cnt;
void add_edge(int u, int v, ll w){
    cnt++;
    e[cnt] = (edge){v, head[u], w};
    head[u] = cnt;
}
ll ans;
void dfs(int u, int f){
    int num = 0;
    for(int i = head[u]; ~i; i = e[i].nex){
        if(e[i].v == f) continue;
        dfs(e[i].v, u);
        num += dp[e[i].v];
        if(dp[e[i].v] % 2) ans += e[i].w;
    }
    dp[u] = num + 1;
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        memset(head, -1, sizeof(head)); cnt = 0;
        ans = 0;
        scanf("%d", &n);
        int u, v; ll w;
        for(int i = 1; i < n; i++){
            scanf("%d%d%lld", &u, &v, &w);
            add_edge(u, v, w); add_edge(v, u, w);
        }
        dfs(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}