tri-βutree [yukicoder 898]

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

前提知識

• LCA

解説

https://yukicoder.me/submissions/387102

頂点数が最小で連結な部分グラフを持ってくるが、
これはx-y, x-z, y-z間の最小パスで使われる頂点を集めたものになる。
これは直感的に分かるかもしれない。
ここで、x->y->z->xのように一筆書きをしてみると、全ての辺はちょうど2回ずつ通っている。
そのため、
(x->yでのパスの重みの総和) + (y->zでのパスの重みの総和) + (z->xでのパスの重みの総和)
の半分が答えになる。
あとは、パスの重みの総和を高速に計算する方法が分かれば解ける。

これは典型問題で、LCAとDFSを使って解くのが、常套。
LCAが分からない場合は、先にどこかで勉強しよう。
(a->bでのパスの重みの総和)は、まず、aとbのLCAを計算する。
LCAをlca(a,b)とすると、(a->bでのパスの重みの総和)は、
(0->aでのパスの重みの総和) + (0->bでのパスの重みの総和) - 2*(0->lca(a,b)でのパスの重みの総和)
となる。
(0->aでのパスの重みの総和)は、DFSをして前計算しておく。
自分のプログラムでは
sm[a] := 0->aでのパスの重みの総和
としている。

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 x, y, z;
        cin >> x >> y >> z;

        ll ans = 0;
        ans += get(x, y);
        ans += get(y, z);
        ans += get(z, x);
        ans /= 2;

        printf("%lld\n", ans);
    }
}