結果

問題 No.898 tri-βutree
ユーザー Y17Y17
提出日時 2019-10-04 21:45:31
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 504 ms / 4,000 ms
コード長 2,562 bytes
コンパイル時間 1,545 ms
コンパイル使用メモリ 172,128 KB
実行使用メモリ 37,620 KB
最終ジャッジ日時 2024-11-08 22:01:32
合計ジャッジ時間 11,341 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define int long long

//最小共通祖先

//コンストラクタ(g) : 木Gで初期化
//build() : 構築する
//query(v, u): 頂点vとuの最小共通祖先を返す

// G : vector<vector<int>>
//木は根付き木でなくてもよい

template< typename G >
struct DoublingLowestCommonAncestor {
    const int LOG;
    vector< int > dep;
    const G &g;
    vector< vector< int > > table;

    DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
        table.assign(LOG, vector< int >(g.size(), -1));
    }

    void dfs(int idx, int par, int d) {
        table[0][idx] = par;
        dep[idx] = d;
        for(auto &to : g[idx]) {
            if(to != par) dfs(to, idx, d + 1);
        }
    }

    void build() {
        dfs(0, -1, 0);
        for(int k = 0; k + 1 < LOG; k++) {
            for(int i = 0; i < table[k].size(); i++) {
                if(table[k][i] == -1) table[k + 1][i] = -1;
                else table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }

    int query(int u, int v) {
        if(dep[u] > dep[v]) swap(u, v);
        for(int i = LOG - 1; i >= 0; i--) {
            if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
        }
        if(u == v) return u;
        for(int i = LOG - 1; i >= 0; i--) {
            if(table[i][u] != table[i][v]) {
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
};

vector<pair<int, int> > graph[100010];
bool used[100010];

vector<vector<int> > tree(100010);
int deep[100010];

void dfs(int idx, int d){
    used[idx] = true;
    deep[idx] = d;

    for(int i = 0;i < graph[idx].size();i++){
        if(!used[graph[idx][i].first]){
            tree[idx].push_back(graph[idx][i].first);
            dfs(graph[idx][i].first, graph[idx][i].second + d);
        }
    }
    return;
}


signed main(){
    int n;
    cin >> n;

    for(int i = 0;i < n-1;i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    dfs(0, 0);

    DoublingLowestCommonAncestor<vector<vector<int>> > lca(tree);
    lca.build();

    auto get = [&](int a, int b){
        return deep[a] + deep[b] - deep[lca.query(a, b)] * 2;
    };

    int q;
    cin >> q;

    for(int i = 0;i < q;i++){
        int a, b, c;
        cin >> a >> b >> c;
        int ans = get(a, b) + get(b, c) + get(c, a);

        cout << ans / 2 << endl;
    }

    return 0;
}
0