NC13886 Shortest Path

题意

给定一棵树，有 $~n~$ 个节点（ $~n~$ 为偶数）。将 $n$ 个节点分成 $n/2$ 组，每组有 $2$ 个节点 $u,v$ ，每组的值为 $u$ 到 $v$ 的树上路径和，总答案为每一组的和。求答案最小值。

分析

这是一道贪心题。
首先一个点和另一个点的距离不会超过两条边，这个画画图即可看出。
于是我们可以知道，最优情况下，一个点的配对点一定是它的父亲或兄弟节点。
考虑以 $u$ 为根的子树和它的儿子节点。
如果节点 $v$ 已经用过了，那显然不用再用它了。没用过就入队。
那么我们得到的队列全是没用过的儿子节点。
最优情况肯定是将儿子节点两两相连。但是会出现奇数个节点的情况，这时候只用将它和 $u$ 相连就可以了。
事实上，我们甚至不用一个队列。如果儿子节点没用过，就直接把这条边的边权加入答案中即可。如果有奇数个没用过的儿子，就标记 $u$ 用过。
细节可以看代码。

代码如下

#include <bits/stdc++.h>
#define N 20005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
struct node{
    int a, b, c, n;
}d[N * 2];
int h[N], fa[N], v[N], cnt;
LL ans;
void cr(int a, int b, int c){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b, c, tot = 0;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        c = d[i].c;
        if(b == fa[a]) continue;
        fa[b] = a;
        dfs(b);
        if(!v[b]) tot++, v[b] = 1, ans += c;
    }
    if(tot % 2) v[a] = 1;
}
int main(){
    int i, j, n, m, T, a, b, c;
    T = read();
    while(T--){
        cnt = ans = 0;
        memset(v, 0, sizeof(v));
        memset(fa, 0, sizeof(fa));
        memset(h, 0, sizeof(h));
        n = read();
        for(i = 1; i < n; i++){
            a = read(); b = read(); c = read();
            cr(a, b, c);
            cr(b, a, c);
        }
        dfs(1);
        printf("%lld\n", ans);
    }
    return 0;
}