G6018 [GESP202509 六级] 货物运输 题解

知识点：树遍历、树上距离、贪心。

解题思路

求树边权总和sum和根1到每点的距离，答案为2sum减去最远距离。

为什么正确

非终点路径上的每条边必须往返，终点路径可以仅走一次；让终点最远可最大化免去的回程距离。

易错点

起点固定为1，不能直接用任意树直径；树边权与总路程用long long。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<pair<int,long long>>>g(n+1);
    long long sum=0;
    for(int i=1;i<n;i++) {
        int u,v;
        long long w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        sum+=w;
    }
    vector<int>p(n+1),q= {
        1
    }
    ;
    vector<long long>d(n+1);
    for(int i=0;i<(int)q.size();i++) {
        int u=q[i];
        for(auto [v,w]:g[u])if(v!=p[u]) {
            p[v]=u;
            d[v]=d[u]+w;
            q.push_back(v);
        }
    }
    cout<<2*sum-*max_element(d.begin(),d.end());
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。