#1180433 (C++23(gcc16)) No.1094 木登り / Climbing tree

• 問題: No.1094 木登り / Climbing tree
• ユーザー: あるふぁ
• 提出日時: 2026-08-30 11:46:39
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 639 ms / 2,000 ms
• コード長: 2,387 bytes
• コンパイル時間: 4,664 ms
• コンパイル使用メモリ: 364,484 KB
• 実行使用メモリ: 55,040 KB
• 最終ジャッジ日時: 2026-08-30 11:47:03
• 合計ジャッジ時間: 22,208 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 26

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct lca{
    int n, log;
    vector<vector<int>> par;
    vector<vector<int>> graph;
    vector<int> dep;
    lca(int n) : n(n){
        log = 1;
        while ((1 << log) <= n) log++;
        graph.resize(n);
        par.assign(n, vector<int>(log, -1));
        dep.resize(n);
    }
    void add_edge(int u, int v){
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    void build(int root = 0){
        queue<int> q;
        q.push(root);
        par[root][0] = -1;
        dep[root] = 0;
        while (!q.empty()){
            int v = q.front();
            q.pop();
            for (int nv : graph[v]){
                if (nv == par[v][0]) continue;
                par[nv][0] = v;
                dep[nv] = dep[v]+1;
                q.push(nv);
            }
        }
        for (int k = 1; k < log; k++){
            for (int v = 0; v < n; v++){
                if (par[v][k-1] < 0){
                    par[v][k] = -1;
                }
                else{
                    par[v][k] = par[par[v][k-1]][k-1];
                }
            }
        }
    }
    int query(int u, int v){
        if (dep[u] < dep[v]) swap(u, v);
        int sum = dep[u]-dep[v];
        for (int k = 0; k < log; k++){
            if (sum & (1 << k)){
                if (u == -1) break;
                u = par[u][k];
            }
        }
        if (u == v) return u;
        for (int k = log-1; k >= 0; k--){
            if (par[u][k] != par[v][k]){
                u = par[u][k];
                v = par[v][k];
            }
        }
        return par[u][0];
    }
};

int main(){
    int N;
    cin >> N;
    vector<vector<pair<int, int>>> G(N);
    lca H(N);
    for (int i = 1; i < N; i++){
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        H.add_edge(u, v);
    }

    vector<ll> dist(N, 0);
    auto dfs = [&](auto&& self, int n, int p) -> void{
        for (auto [v, w] : G[n]) if (v != p){
            dist[v] = dist[n]+w;
            self(self, v, n);
        }
    };
    dfs(dfs, 0, -1);

    int Q;
    cin >> Q;
    H.build();
    while (Q--){
        int a, b, c;
        cin >> a >> b;
        a--, b--;
        c = H.query(a, b);
        cout << dist[a]+dist[b]-2*dist[c] << endl;
    }
}