結果

問題 No.898 tri-βutree
ユーザー kyawa
提出日時 2021-12-09 16:22:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 758 ms / 4,000 ms
コード長 3,713 bytes
コンパイル時間 2,935 ms
コンパイル使用メモリ 224,368 KB
最終ジャッジ日時 2025-01-26 07:15:59
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template < typename Element = long >
class SparseTable{
public:
    function<Element(Element, Element)> operation;
    vector<vector<Element>> table;
    vector<long> cf;
    
    SparseTable(vector<Element>& v, Element e, function<Element(Element, Element)> operation) : operation(operation){
        long isiz = v.size();
        long jsiz = 0;
        while((1 << jsiz) <= isiz) jsiz++;
        table.resize(isiz, vector<Element>(jsiz, e));
        for(long i = 0; i < isiz; i++)table[i][0] = v[i];
        for(long j = 1; j < jsiz; j++){
            for(long i = 0; i + (1 << (j - 1)) < isiz; i++){
                table[i][j] = operation(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
            }
        }
        cf.resize(isiz + 1);
        for(long i = 2; i <= isiz; i++) cf[i] = cf[i >> 1] + 1;
    }
    
    Element query(long l, long r/*半開区間*/){
        assert(l < r);
        long b = cf[r - l];
        return operation(table[l][b], table[r - (1 << b)][b]);
    }
};

class LowestCommonAncestor{
private:
    long N;
    vector<bool> visited;
    vector<vector<long> > Tree;
    vector<vector<long> > STtable;
    vector<long> STcf;
    
    void make_EularTour(long vis){
        EularTour.push_back(depth[vis] * N + vis);
        visited[vis] = true;
        for(auto e : Tree[vis]){
            if(visited[e]) continue;
            depth[e] = depth[vis] + 1;
            make_EularTour(e);
            EularTour.push_back(depth[vis] * N + vis);
        }
    }
    
    void make_SparseTable(){
        SparseTable<long> st(EularTour, LONG_MAX, [](long a, long b){return min(a, b);});
        STtable = st.table;
        STcf = st.cf;
    }
    
    void make_first(){
        long index = 0;
        for(auto e : EularTour){
            first_index[e % N] = min(first_index[e % N], index);
            index++;
        }
    }
public:
    vector<long> depth;
    vector<long> EularTour;
    vector<long> first_index;
    
    LowestCommonAncestor(vector<vector<long>>& tree, long root) : Tree(tree){
        N = Tree.size();
        visited.resize(N, false);
        depth.resize(N, 0);
        first_index.resize(N, INT_MAX);
        make_EularTour(root);
        make_SparseTable();
        make_first();
    }
    
    long query(long l, long r){
        long ltmp = l, rtmp = r;
        l = min(first_index[ltmp], first_index[rtmp]); r = max(first_index[ltmp], first_index[rtmp]) + 1;
        long b = STcf[r - l];
        return min(STtable[l][b], STtable[r - (1 << b)][b]) % N;
    }
};

int main(){
    long N; cin >> N;
    vector<vector<long>> tree(N);
    vector<vector<pair<long,long>>> tree_weight(N);
    for(long i = 0; i < N - 1; i++){
        long u, v, w; cin >> u >> v >> w;
        tree[u].push_back(v);
        tree[v].push_back(u);
        tree_weight[u].push_back({v, w});
        tree_weight[v].push_back({u, w});
    }
    
    vector<long> dist(N, 0);
    vector<bool> bfs_vis(N, false); bfs_vis[0] = true;
    stack<pair<long,long>> bfs; bfs.push({0, 0});
    while(not bfs.empty()){
        auto [e, w] = bfs.top(); bfs.pop();
        for(auto [e2, w2] : tree_weight[e]){
            if(bfs_vis[e2]) continue;
            bfs_vis[e2] = true;
            dist[e2] = w + w2;
            bfs.push({e2, w + w2});
        }
    }
    
    LowestCommonAncestor lca(tree, 0);
    
    long Q; cin >> Q;
    while(Q--){
        long x, y, z; cin >> x >> y >> z;
        long dxy = dist[x] + dist[y] - 2 * dist[lca.query(x, y)];
        long dyz = dist[y] + dist[z] - 2 * dist[lca.query(y, z)];
        long dzx = dist[z] + dist[x] - 2 * dist[lca.query(z, x)];
        cout << (dxy + dyz + dzx) / 2 << '\n';
    }
}
0