20200403 Shortest Path

下载pdf，获得更好的阅读体验。

提取码：f1ji

题意翻译

有一棵有 个结点的树（ 为偶数）将其划分为 对点对，使得点对间距离综合最小，求该最小值。

多测， 组测试数据。

题解

为了值最小，显然尽量不选重的。

对于一棵子树，如果它的大小是偶数，则可以在这个子树内完成配对。

如果它是奇数，则有一个点要继续向上配对。无论是和根结点还是和其他子树，这个点额外的贡献都是父节点往这个子树的连边。

只要 dfs 一遍就可以得出答案。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 10000 + 7;
const int maxm = 20000 + 7;

int T;
int n, Head[maxn], to[maxm], Next[maxm], w[maxm], tot;

void addedge(int x, int y, int z) {
    to[++tot] = y, Next[tot] = Head[x], Head[x] = tot, w[tot] = z;
}
void add(int x, int y, int z) {
    addedge(x, y, z); addedge(y, x, z);
}

void clear(void) {
    tot = 0;
    memset(Head, 0, sizeof(Head));
    memset(Next, 0, sizeof(Next));
}

void Init(void) {
    scanf("%d", &n);
    for(int i = 1, x, y, z; i < n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
}

LL ans;

int dfs(int x, int f, LL l) {
    int size = 1;
    for(int i = Head[x]; i; i = Next[i]) {
        int y = to[i];
        if(y == f) continue;
        size += dfs(y, x, (LL)w[i]);
    }
    if(size & 1) ans += l;
    return size;
}

void Work(void) {
    ans = 0;
    dfs(1, 0, 0);
    printf("%lld\n", ans);
}

int main(void) {
    scanf("%d", &T);
    while(T--) {
        clear();
        Init();
        Work();
    }
}