#952233 (C++17) No.901 K-ary εxtrεεmε

• 問題: No.901 K-ary εxtrεεmε
• ユーザー: ikefumy
• 提出日時: 2024-02-18 16:35:32
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 208 ms / 3,000 ms
• コード長: 7,858 bytes
• コンパイル時間: 2,956 ms
• コンパイル使用メモリ: 223,380 KB
• 最終ジャッジ日時: 2025-02-19 16:16:24
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 29

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

struct undirected_graph {
public:
    int n;
    vector<vector<int>> g;

    undirected_graph(int _n = 0) : n(_n), g(_n) {}
    void add_edge(int u, int v) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        g[u].push_back(v);
        g[v].push_back(u);
    }
};

struct LCA : undirected_graph {
    bool built = false;
    int logn = 0, s, B, logB = 0;
    vector<int> euler_tour, depth, in, out, log_table, diff;
    vector<vector<int>> sparse_table;
    vector<vector<vector<int>>> table_lookup;
    LCA(int _n) : undirected_graph(_n), depth(_n), in(_n), out(_n) {
        while ((1 << logn) <= 2 * n - 1) logn++;
        s = max(1, logn / 2);
        B = (2 * n - 2) / s + 1;
        while ((1 << logB) <= B) logB++;

        diff = vector(B, 0);
        log_table = vector(B, 0);
        sparse_table = vector(B, vector<int>(logB, -1));
        table_lookup = vector(1 << (s - 1), vector(s, vector<int>(s, -1)));
        // table_loopupの構築
        for (int i = 0; i < 1 << (s - 1); i++) {
            for (int l = 0; l < s; l++) {
                int ans = l, mn = 0, val = 0;
                for (int r = l; r < s; r++) {
                    table_lookup[i][l][r] = ans;
                    val += ((i >> r & 1) ? 1 : -1);
                    if (val < mn) {
                        mn = val;
                        ans = r + 1;
                    }
                }
            }
        }
    }

    void dfs(int v, int p) {
        in[v] = euler_tour.size();
        euler_tour.emplace_back(v);
        for (auto&& u : g[v]) {
            if (u == p) continue;
            depth[u] = depth[v] + 1;
            dfs(u, v);
            euler_tour.emplace_back(v);
        }
        out[v] = euler_tour.size() - 1;
    }

    int get_min(const int& u, const int& v) {
        if (u == -1) return v;
        else if (v == -1) return u;
        else return depth[u] < depth[v] ? u : v;
    }

    void build() {
        built = true;
        dfs(0, -1);

        // table_lookup用の配列
        for (int i = 0; i < 2 * n - 2; i++) {
            if (i / s != (i + 1) / s) continue;
            if (depth[euler_tour[i]] < depth[euler_tour[i + 1]]) {
                diff[i / s] |= 1 << (i % s);
            }
        }

        // sparse tableの構築
        for (int i = 0; i < 2 * n - 1; i++) {
            int b = i / s;
            sparse_table[b][0] = get_min(sparse_table[b][0], euler_tour[i]);
        }
        for (int j = 1; j < logB; j++) {
            for (int i = 1 << j; i < min(1 << (j + 1), B); i++) {
                log_table[i] = j;
            }
            for (int i = 0; i < B; i++) {
                if (i + (1 << (j - 1)) >= B) break;
                int v1 = sparse_table[i][j - 1];
                int v2 = sparse_table[i + (1 << (j - 1))][j - 1];
                sparse_table[i][j] = get_min(sparse_table[i][j - 1], sparse_table[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int get_lca(int u, int v) {
        assert(built);
        if (in[u] > in[v]) swap(u, v);
        int ret = 0;
        int bu = in[u] / s, bv = in[v] / s;
        if (bu == bv) {
            ret = euler_tour[bu * s + table_lookup[diff[bu]][in[u] % s][in[v] % s]];
        } else {
            ret = get_min(euler_tour[bu * s + table_lookup[diff[bu]][in[u] % s][s - 1]], euler_tour[bv * s + table_lookup[diff[bv]][0][in[v] % s]]);
            if (bv - 1 - bu > 0) {
                int len = bv - 1 - bu;
                ret = get_min(ret, sparse_table[bu + 1][log_table[len]]);
                ret = get_min(ret, sparse_table[bv - (1 << log_table[len])][log_table[len]]);
            }
        }
        return ret;
    }
};

struct auxiliary_tree : LCA {
    vector<int> used;
    auxiliary_tree(int _n) : LCA(_n), used(_n) {}
    void build() {
        LCA::build();
    }

    pair<vector<vector<int>>, vector<int>> get_at(vector<int> v) {
        sort(v.begin(), v.end(), [&](int a, int b) {
            return in[a] < in[b];
        });
        
        for (auto u : v) used[u] = true;
        for (int i = 1; i < (int)v.size(); i++) {
            int lca = get_lca(v[i - 1], v[i]);
            if (!used[lca]) {
                used[lca] = true;
                v.emplace_back(lca);
            }
        }

        sort(v.begin(), v.end(), [&](int a, int b) {
            return in[a] < in[b];
        });

        vector<vector<int>> retg(v.size());
        stack<int> rem;
        for (int i = 0; i < (int)v.size(); i++) {
            used[v[i]] = false;
            while (!rem.empty() && out[v[rem.top()]] < in[v[i]]) rem.pop();
            if (!rem.empty()) {
                int a = rem.top(), b = i;
                retg[a].push_back(b);
                retg[b].push_back(a);
            }
            rem.push(i);
        }

        return {retg, v};
    }
};

int N, u, v, w, Q;
vector<pll> G[100010];
ll len[100010];

void dfs(int v, int p) {
    for (auto&& [u, w] : G[v]) {
        if (u == p) continue;
        len[u] = len[v] + w;
        dfs(u, v);
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> N;
    auxiliary_tree at(N);
    rep (i, N - 1) {
        cin >> u >> v >> w;
        at.add_edge(u, v);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    at.build();
    dfs(0, -1);
    cin >> Q;
    rep (i, Q) {
        int k;
        cin >> k;
        vector<int> vs(k);
        rep(j, k) cin >> vs[j];
        auto [g, label] = at.get_at(vs);
        ll ans = 0;
        rep (i, g.size()) {
            for (auto&& u : g[i]) {
                if (i < u) continue;
                ans += abs(len[label[u]] - len[label[i]]);
            }
        }
        cout << ans << '\n';
    }
}