結果

問題 No.898 tri-βutree
ユーザー xuzijian629xuzijian629
提出日時 2019-10-04 21:33:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 234 ms / 4,000 ms
コード長 2,905 bytes
コンパイル時間 2,825 ms
コンパイル使用メモリ 221,000 KB
実行使用メモリ 69,856 KB
最終ジャッジ日時 2024-11-08 21:47:48
合計ジャッジ時間 7,923 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
69,856 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 207 ms
63,256 KB
testcase_08 AC 211 ms
63,392 KB
testcase_09 AC 206 ms
63,384 KB
testcase_10 AC 234 ms
63,256 KB
testcase_11 AC 207 ms
63,384 KB
testcase_12 AC 197 ms
63,256 KB
testcase_13 AC 197 ms
63,380 KB
testcase_14 AC 205 ms
63,412 KB
testcase_15 AC 206 ms
63,260 KB
testcase_16 AC 199 ms
63,256 KB
testcase_17 AC 198 ms
63,388 KB
testcase_18 AC 205 ms
63,252 KB
testcase_19 AC 197 ms
63,128 KB
testcase_20 AC 204 ms
63,240 KB
testcase_21 AC 203 ms
63,380 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