結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:30:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 3,000 ms |
コード長 | 2,503 bytes |
コンパイル時間 | 1,893 ms |
コンパイル使用メモリ | 189,508 KB |
実行使用メモリ | 33,812 KB |
最終ジャッジ日時 | 2024-10-04 06:23:03 |
合計ジャッジ時間 | 6,035 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lint = long long;template<class T = int> using V = vector<T>;template<class T = int> using VV = V< V<T> >;namespace LCA {using T = lint;struct Edge { int to; T w; };T op(const T& x, const T& y) { return x + y; }constexpr T e = 0;V<> dep, in;VV<> par;VV<T> val;void init(const VV<Edge>& g, int r) {int n = g.size();dep.resize(n);in.resize(n);par.assign(__lg(2 * n - 1), V<>(n, -1));val.assign(__lg(2 * n - 1), V<T>(n, e));auto dfs = [&](const auto& dfs, int v, int p) -> void {static int t = 0;in[v] = t++;for (const auto& e : g[v]) if (e.to != p) {dep[e.to] = dep[v] + 1;par[0][e.to] = v;val[0][e.to] = e.w;dfs(dfs, e.to, v);}};dep[r] = 0;dfs(dfs, r, -1);for (int k = 1; k < (int) par.size(); ++k) {for (int v = 0; v < n; ++v) {if (par[k - 1][v] == -1) continue;par[k][v] = par[k - 1][par[k - 1][v]];val[k][v] = op(val[k - 1][v], val[k - 1][par[k - 1][v]]);}}}int get_par(int v, int h) {for (int k = 0; h > 0; h >>= 1, ++k) {if (v == -1) break;if (h & 1) v = par[k][v];}return v;}int lca(int u, int v) {if (dep[u] > dep[v]) swap(u, v);v = get_par(v, dep[v] - dep[u]);if (u == v) return u;for (int k = par.size() - 1; k >= 0; --k) {if (par[k][u] != par[k][v]) {u = par[k][u];v = par[k][v];}}return par[0][u];}T get_val(int v, int h) {T res = e;for (int k = 0; h > 0; h >>= 1, ++k) {if (v == -1) break;if (h & 1) {res = op(res, val[k][v]);v = par[k][v];}}return res;}T acc(int u, int v) {int a = lca(u, v);return op(get_val(v, dep[v] - dep[a]), get_val(u, dep[u] - dep[a]));}}int main() {cin.tie(nullptr); ios::sync_with_stdio(false);int n; cin >> n;VV<LCA::Edge> g(n);for (int _ = 0; _ < n - 1; ++_) {int u, v, w; cin >> u >> v >> w;g[u].emplace_back(LCA::Edge{v, w});g[v].emplace_back(LCA::Edge{u, w});}LCA::init(g, 0);int q; cin >> q;while (q--) {int k; cin >> k;V<> x(k); for (auto&& e : x) cin >> e;sort(begin(x), end(x), [&](int u, int v) { return LCA::in[v] < LCA::in[u]; });lint res = 0;for (int i = 0; i < k; ++i) {res += LCA::acc(x[i], x[(i + 1) % k]);}cout << res / 2 << '\n';}}