結果

問題 No.901 K-ary εxtrεεmε
コンテスト
ユーザー ebi_fly
提出日時 2023-11-24 15:34:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 335 ms / 3,000 ms
コード長 5,880 bytes
コンパイル時間 3,796 ms
コンパイル使用メモリ 279,136 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-26 08:37:27
合計ジャッジ時間 12,525 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test/tree/yuki_901.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/901"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 2 "tree/HeavyLightDecomposition.hpp"

#line 4 "tree/HeavyLightDecomposition.hpp"

namespace lib {

using namespace std;

struct HeavyLightDecomposition {
  private:
    void dfs_sz(int v) {
        for (auto &nv : g[v]) {
            if (nv == par[v]) continue;
            par[nv] = v;
            depth[nv] = depth[v] + 1;
            dfs_sz(nv);
            sz[v] += sz[nv];
            if (sz[nv] > sz[g[v][0]] || g[v][0] == par[v]) swap(nv, g[v][0]);
        }
    }

    void dfs_hld(int v) {
        in[v] = t++;
        for (auto nv : g[v]) {
            if (nv == par[v]) continue;
            nxt[nv] = (nv == g[v][0] ? nxt[v] : nv);
            dfs_hld(nv);
        }
        out[v] = t;
    }

    // [u, v) パスの取得 (v は u の祖先)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]) {
            res.emplace_back(in[u], in[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u, v] パスの取得 (u は v の祖先)
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{in[u] + 1, in[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(in[nxt[v]], in[v]);
        return res;
    }

  public:
    HeavyLightDecomposition(const vector<vector<int>> &gh, int root = 0)
        : n(gh.size()),
          g(gh),
          sz(n, 1),
          in(n),
          out(n),
          nxt(n),
          par(n, -1),
          depth(n, 0) {
        nxt[root] = root;
        dfs_sz(root);
        dfs_hld(root);
    }

    int idx(int u) const {
        return in[u];
    }

    int lca(int u, int v) const {
        while (nxt[u] != nxt[v]) {
            if (in[u] < in[v]) swap(u, v);
            u = par[nxt[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int distance(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }

    template <class F>
    void path_noncommutative_query(int u, int v, bool vertex,
                                   const F &f) const {
        int l = lca(u, v);
        for (auto [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(in[l], in[l] + 1);
        for (auto [a, b] : descend(l, v)) f(a, b + 1);
    }

    template <class F> void subtree_query(int u, bool vertex, const F &f) {
        f(in[u] + int(!vertex), out[u]);
    }

    int parent(int v) {
        return par[v];
    }

    std::vector<std::pair<int,int>> lca_based_auxiliary_tree(std::vector<int>);

  private:
    int n, t = 0;
    vector<vector<int>> g;
    vector<int> sz, in, out, nxt, par, depth;
};

}  // namespace lib
#line 2 "tree/lca_based_auxiliary_tree.hpp"

#line 4 "tree/lca_based_auxiliary_tree.hpp"

namespace lib {

using namespace std;

vector<pair<int, int>> HeavyLightDecomposition::lca_based_auxiliary_tree(
    vector<int> vs) {
    if (vs.empty()) return {};
    sort(all(vs), [&](int u, int v) { return in[u] < in[v]; });
    auto s = vs;
    for(int i = 1; i < int(vs.size()); i++) {
        s.emplace_back(lca(vs[i-1], vs[i]));
    }
    std::sort(all(s), [&](int u, int v) { return in[u] < in[v]; });
    s.erase(unique(all(s)), s.end());
    stack<int> st;
    st.push(s[0]);
    int sz = s.size();
    std::vector<std::pair<int,int>> dfs_order(sz);
    dfs_order[0] = {s[0], -1};
    rep(i,1,sz) {
        int v = s[i];
        while(!st.empty()) {
            int u = st.top();
            if(in[u] <= in[v] && in[v] < out[u]) {
                break;
            }
            else {
                st.pop();
            }
        }
        assert(!st.empty());
        int par = st.top();
        dfs_order[i] = {v, par};
        st.push(v);
    }
    return dfs_order;
}

}  // namespace lib
#line 6 "test/tree/yuki_901.test.cpp"

using namespace lib;

int main() {
    int n;
    std::cin >> n;
    std::vector g(n, std::vector<int>());
    std::vector<std::tuple<int, int, ll>> edges(n - 1);
    for (auto &[u, v, w] : edges) {
        std::cin >> u >> v >> w;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    HeavyLightDecomposition hld(g);
    std::vector<ll> sum(n + 1, 0);
    for (auto [u, v, w] : edges) {
        if (hld.parent(v) == u) std::swap(u, v);
        sum[hld.idx(u) + 1] += w;
    }
    rep(i, 0, n) {
        sum[i + 1] += sum[i];
    }
    auto path_sum = [&](int u, int v) -> ll {
        ll ret = 0;
        auto f = [&](int l, int r) -> void {
            if (l > r) std::swap(l, r);
            ret += sum[r] - sum[l];
        };
        hld.path_noncommutative_query(u, v, false, f);
        return ret;
    };
    int q;
    std::cin >> q;
    while (q--) {
        int k;
        std::cin >> k;
        std::vector<int> vs(k);
        for(auto &v: vs) std::cin >> v;
        ll ans = 0;
        auto auxiliary_tree = hld.lca_based_auxiliary_tree(vs);
        for (auto [v, par] : auxiliary_tree) {
            if (par != -1) {
                ans += path_sum(v, par);
            }
        }
        std::cout << ans << '\n';
    }
    return 0;
}
0