結果

問題 No.898 tri-βutree
ユーザー xuzijian629xuzijian629
提出日時 2019-10-04 21:33:24
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 210 ms / 4,000 ms
コード長 2,905 bytes
コンパイル時間 2,715 ms
コンパイル使用メモリ 219,952 KB
実行使用メモリ 68,204 KB
最終ジャッジ日時 2023-08-08 15:48:15
合計ジャッジ時間 8,614 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
68,204 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 202 ms
63,248 KB
testcase_08 AC 203 ms
63,328 KB
testcase_09 AC 203 ms
63,240 KB
testcase_10 AC 201 ms
63,220 KB
testcase_11 AC 196 ms
63,316 KB
testcase_12 AC 201 ms
63,136 KB
testcase_13 AC 201 ms
63,228 KB
testcase_14 AC 210 ms
63,256 KB
testcase_15 AC 208 ms
63,080 KB
testcase_16 AC 200 ms
63,072 KB
testcase_17 AC 208 ms
63,080 KB
testcase_18 AC 201 ms
63,256 KB
testcase_19 AC 203 ms
63,232 KB
testcase_20 AC 202 ms
63,124 KB
testcase_21 AC 209 ms
63,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T>
struct SparseTable {
    vector<vector<T>> st;
    vector<int> lookup;

    SparseTable(const vector<T>& v) {
        int b = 0;
        while ((1 << b) <= v.size()) b++;
        st.assign(b, vector<T>(1 << b));
        for (int i = 0; i < v.size(); i++) {
            st[0][i] = v[i];
        }
        for (int i = 1; i < b; i++) {
            for (int j = 0; j + (1 << i) <= 1 << b; j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
        lookup.resize(v.size() + 1);
        for (int i = 2; i < lookup.size(); i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }

    T query(int l, int r) {
        int b = lookup[r - l];
        return min(st[b][l], st[b][r - (1 << b)]);
    }
};

struct LCA {
    int n, k = 0;
    vector<vector<int>> adj;
    vector<int> vs, depth, id, D;
    SparseTable<pair<int, int>>* st;

    void dfs(int v, int p, int d) {
        id[v] = k;
        vs[k] = v;
        depth[k++] = d;
        D[v] = d;
        for (int s : adj[v]) {
            if (s != p) {
                dfs(s, v, d + 1);
                vs[k] = v;
                depth[k++] = d;
            }
        }
    }

    LCA(const vector<vector<int>>& adj)
        : n(adj.size()), adj(adj), vs(2 * adj.size() - 1), depth(2 * adj.size() - 1), id(adj.size()), D(adj.size()) {
        dfs(0, -1, 0);
        vector<pair<int, int>> ds;
        for (int i = 0; i < depth.size(); i++) {
            ds.emplace_back(depth[i], i);
        }
        st = new SparseTable<pair<int, int>>(ds);
    }

    int lca(int u, int v) { return vs[st->query(min(id[u], id[v]), max(id[u], id[v]) + 1).second]; }

    int dist(int u, int v) { return D[u] + D[v] - 2 * D[lca(u, v)]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<pair<int, int>>> adj(n);
    vector<vector<int>> adj2(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
        adj2[a].push_back(b);
        adj2[b].push_back(a);
    }
    LCA lca(adj2);
    vector<long long> depth(n);
    function<void(int, int, long long)> dfs = [&](int v, int p, long long d) {
        depth[v] = d;
        for (auto& s : adj[v]) {
            if (s.first != p) {
                dfs(s.first, v, d + s.second);
            }
        }
    };
    dfs(0, -1, 0);
    int q;
    cin >> q;

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

    while (q--) {
        int a, b, c;
        cin >> a >> b >> c;
        long long ans = 0;
        ans += get_path_weight(a, b);
        ans += get_path_weight(b, c);
        ans += get_path_weight(c, a);
        ans /= 2;
        cout << ans << '\n';
    }
}
0