本質 : 条件を緩くした場合の問題を考えると見通しがよくなる場合がある

必ず最初に出発した頂点に帰らなければ行けないという制約で考えると必要なコストは $\sum_{i=1}^{n-1} (C_i \times 2)$ になる。

グラフをぐるっと一周するような回り方をするときに省ける距離を考える。

つまりグラフのある頂点 $u$ からある頂点 $v$ $(u \neq v)$ までの距離を一周する経路から外してもすべての頂点は訪れることは出来る。

つまり

$$ \sum_{i=1}^{n-1} (C_i \times 2) - 木の直径 $$

が答えになるということである。

ここで木の直径について考える。

直径はある頂点 $u$ からある頂点 $v$ までの距離が一番長くなるように決めたときの距離(重み)である。

直径を求めるアルゴリズム

上記より2回DFSを行えば直径が求められる。

実装が少しややこしいが素直に覚えてしまう方がいいと思った。

auto dfs = [&](auto f, int v, ll d = 0, int p = -1) -> pair<ll, int> {
        auto res = make_pair(d, v);
        for (auto e : g[v]) {
            if (e.to == p) continue;
            res = max(res, f(f, e.to, d + e.cost, v));
        }
        return res;
    };

e は to (行き先)と cost (重み)が入っている構造体である。