問題概要

頂点数 $N$ の木が与えられる。 $i$ 番目の辺は、頂点 $A_{i}$ と頂点 $B_{i}$ を結んでおり、長さは $C_{i}$ である。

いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$

考えたこと

もし仮に、すべての街を 1 度以上訪れた上で、出発した街に戻ってくる必要もあるならば、下図のようにすべての辺をちょうど 2 回ずつ通ることとなる。

これに対し、出発地点を $s$ 、終了地点を $t$ として、 $s$ から全ての街を 1 度以上訪れて $t$ へと至るウォークは、上記のルートから $s$ - $t$ パスを除外したものとなる。

よって、「すべての辺の重みの総和の 2 倍」から、「木の 2 点間のパスの重みの総和の最大値」を引いたものが答えとなる。

「木の 2 点間のパスの重みの総和の最大値」は直径と呼ばれる。直径を求めるためには、次の 2 ステップの処理を実行すればよい。

木から頂点を 1 個選んで、その頂点から最も遠い頂点 $s$ を求める
頂点 $s$ から最も遠い頂点を $t$ としたとき、 $s$ - $t$ パスが直径である

この方法の計算量は $O(N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;

int main() {
    long long N, sum = 0;
    cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int A, B, C;
        cin >> A >> B >> C;
        --A, --B;
        G[A].emplace_back(B, C);
        G[B].emplace_back(A, C);
        sum += C;
    }
    
    auto longest = [&](auto longest, int v, int p) -> pair<long long, int> {
        long long res = 0;
        int res_v = v;
        for (auto e : G[v]) {
            if (e.first == p) continue;
            auto [most, most_v] = longest(longest, e.first, v);
            if (res < e.second + most) {
                res = e.second + most;
                res_v = most_v;
            }
        }
        //cout << v << ", " << p << ": " << res << "(" << res_v << ")" << endl;
        return {res, res_v};
    };
    auto [most, v] = longest(longest, 0, -1);
    auto [res, res_v] = longest(longest, v, -1);
    
    //cout << most << ", " << v << endl;
    //cout << res << ", " << res_v << endl;
    
    cout << sum * 2 - res << endl;
}