結果

問題 No.901 K-ary εxtrεεmε
ユーザー kyawa
提出日時 2021-12-16 20:27:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 558 ms / 3,000 ms
コード長 3,767 bytes
コンパイル時間 2,827 ms
コンパイル使用メモリ 226,060 KB
最終ジャッジ日時 2025-01-26 23:43:08
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

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_w(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_w[u].push_back({v, w});
        tree_w[v].push_back({u, w});
    }
    LowestCommonAncestor lca(tree, 0);
    vector<long> depth(N, -1);
    vector<long> dfs_order(N);
    long ord = 0;
    stack<pair<long,long>> dfs; dfs.push({0, 0});
    while(not dfs.empty()){
        auto [v, w] = dfs.top(); dfs.pop();
        depth[v] = w;
        dfs_order[v] = ord; ord++;
        for(auto [v2, w2] : tree_w[v]){
            if(depth[v2] != -1) continue;
            dfs.push({v2, w + w2});
        }
    }
    long Q; cin >> Q;
    while(Q--){
        long res = 0;
        long K; cin >> K;
        vector<long> t(K);
        for(long i = 0; i < K; i++) cin >> t[i];
        sort(t.begin(), t.end(), [&](auto a, auto b){return dfs_order[a] > dfs_order[b];});
        for(long i = 0; i < K; i++) res += depth[t[i % K]] + depth[t[(i + 1) % K]] - 2 * depth[lca.query(t[i % K], t[(i + 1) % K])];
        cout << res / 2 << '\n';
    }
}
0