K-ary εxtrεεmε [yukicoder 901]

https://yukicoder.me/problems/no/901

前提知識

• LCA

解説

https://yukicoder.me/submissions/387110

この問題の上位互換であるが、本質的には同じ解法を使える。
与えられた頂点をEuler Tourでの順番にソートすると、(v1->v2の距離+v2->v3の距離+...+vN->v1の距離)/2が答えになる。
これはv1->v2->...->vN->v1とすると、辺をちょうど2回だけ通るパスになるためである。
ちょうど2回通る理由としては、Euler TourはDFSで順番に遷移していて、
その順番に並び替えたということは、DFSで訪れるパスのうち一部を削除した形になるためである。

int N;
vector<pair<int, int>> E[101010];
int Q;
//---------------------------------------------------------------------------------------------------
HLDecomposition hld;
ll sm[101010];
void dfs(int cu, int pa = -1) {
    fore(p, E[cu]) {
        int to, c;
        tie(to, c) = p;

        if (pa == to) continue;
        sm[to] = sm[cu] + c;
        dfs(to, cu);
    }
}
ll get(int a, int b) {
    return sm[a] + sm[b] - 2LL * sm[hld.lca(a, b)];
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    
    hld.init(N);
    rep(i, 0, N - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        E[a].push_back({b, c});
        E[b].push_back({a, c});
        hld.add(a, b);
    }

    hld.build();
    dfs(0);

    cin >> Q;
    rep(q, 0, Q) {
        int k; cin >> k;

        vector<pair<int, int>> v;
        rep(i, 0, k) {
            int x;
            cin >> x;
            v.push_back({hld.vid[x], x});
        }
        sort(all(v));

        ll ans = 0;
        int n = v.size();
        rep(i, 0, n) ans += get(v[i].second, v[(i + 1) % n].second);
        ans /= 2;
        printf("%lld\n", ans);
    }
}