题目：https://ac.nowcoder.com/acm/problem/13886

英文劝退：萌新别看到英文题目就被劝退了啊，虽然我也是个英语渣。。。

划重点：Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.这句话说有$n$个城市$n-1$条双向道路，且从任意一个城市可以到达另一个城市，说明是一颗树。

问题：要把$n$个点两两配对，使得两点路径之和最小，$n$一定是偶数。

基本思路：每个点和就近的点配对，问题是当就近的点不止一个时该怎么选择？如下图所示的树中点$s$是选点$a$还是选点$e$亦或者更远的点呢？

结论： 如果某条边连接的子树中的结点个数是奇数则选择该边，是偶数则不选。

• 奇数以子树e为例，如果不选w2边的话，那么e子树中点两两配对必定会剩下一个，剩下的那一个点去和其他点配对的话必定会经过点s，路径长度不小于w2。
• 偶数以子树a为例，如果选了w1边的话，同理a子树中无论怎么配对始终会剩下一个，而剩下的那一个去和其他点配对必定会经过点s，路径长度不小于w1。
• 如果有多个奇数结点的子树，都要选吗？都选的话怎么理解？还是以子树a为例，a有b、c、d三个奇数结点的子树，所以w3、w4、w5三条边都要选。但选了不代表a就一定要和b配对，a可以配对c，然后b和d配对。选了只是说在子树a的最优解决方案中会有w3这条边。
• 以此推到任意子树的解，选择某条边并不是说根结点一定和该边对应的结点配对，而是说在这颗子树的最优解中有这条边，而不关心具体的配对方案。

严谨：是结点而不是节点！！！敲了半天节点感觉怪怪的，幸好百度了一下。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 2e5 + 117;

int t, n;
int u, v;
LL w, sum;
bool vis[MAXN];
struct Edge {
    int v, ne;
    LL w;
} edge[MAXN];
int head[MAXN], tot;
void init() {
    sum = tot = 0;
    memset(vis, false, sizeof(vis));
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, LL w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
int dfs(int id) {
    vis[id] = true;
    int ret = 1, num;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(vis[edge[i].v]) continue;
        num = dfs(edge[i].v);
        if(num & 1) sum += edge[i].w;
        ret += num;
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        init();
        scanf("%d", &n);
        for(int i = 1; i < n; i++) {
            scanf("%d%d%lld", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dfs(1);
        printf("%lld\n", sum);
    }
    return 0;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/131/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。