結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | ebi_fly |
提出日時 | 2023-11-24 15:34:22 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 169 ms
22,144 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 4 ms
5,376 KB |
testcase_03 | AC | 4 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 221 ms
19,072 KB |
testcase_08 | AC | 222 ms
18,944 KB |
testcase_09 | AC | 227 ms
19,072 KB |
testcase_10 | AC | 231 ms
18,944 KB |
testcase_11 | AC | 232 ms
18,944 KB |
testcase_12 | AC | 212 ms
18,944 KB |
testcase_13 | AC | 220 ms
18,944 KB |
testcase_14 | AC | 215 ms
18,944 KB |
testcase_15 | AC | 209 ms
18,944 KB |
testcase_16 | AC | 209 ms
18,944 KB |
testcase_17 | AC | 279 ms
18,944 KB |
testcase_18 | AC | 273 ms
18,944 KB |
testcase_19 | AC | 278 ms
18,944 KB |
testcase_20 | AC | 285 ms
18,944 KB |
testcase_21 | AC | 283 ms
18,944 KB |
testcase_22 | AC | 205 ms
19,328 KB |
testcase_23 | AC | 204 ms
19,328 KB |
testcase_24 | AC | 210 ms
19,328 KB |
testcase_25 | AC | 204 ms
19,328 KB |
testcase_26 | AC | 206 ms
19,328 KB |
testcase_27 | AC | 330 ms
19,072 KB |
testcase_28 | AC | 334 ms
19,072 KB |
testcase_29 | AC | 335 ms
18,944 KB |
ソースコード
#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; }