結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー |
|
提出日時 | 2019-10-04 22:38:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 237 ms / 3,000 ms |
コード長 | 3,252 bytes |
コンパイル時間 | 2,029 ms |
コンパイル使用メモリ | 197,332 KB |
実行使用メモリ | 27,000 KB |
最終ジャッジ日時 | 2024-10-04 06:29:25 |
合計ジャッジ時間 | 7,694 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)#define rep2(i, l, r) for (int i = (l); i < (r); i++)#define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)#define range(a) a.begin(), a.end()using namespace std;using ll = long long;struct HLD {vector<int> label, parent, head;vector<int> L, R;HLD(const vector<vector<int>> &g) : label(g.size()), parent(g.size()), head(g.size()), L(g.size()), R(g.size()) {const int n = g.size();vector<int> size(n, 1);auto dfs = [&](auto dfs, int u, int p) -> void {for (int v : g[u]) if (v != p) {dfs(dfs, v, u);size[u] += size[v];}};dfs(dfs, 0, -1);int k = 0;auto dfs2 = [&](auto dfs, int u, int p, int h) -> void {L[u] = k;label[u] = k++;head[u] = h;parent[u] = p;for (int v : g[u]) if (v != p && size[v] * 2 > size[u]) dfs(dfs, v, u, h);for (int v : g[u]) if (v != p && size[v] * 2 <= size[u]) dfs(dfs, v, u, v);R[u] = k;};dfs2(dfs2, 0, -1, 0);}int lca(int u, int v) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) return u;v = parent[head[v]];}}template<class F> void each(int u, int v, F f) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) {f(label[u], label[v]);return;}f(label[head[v]], label[v]);v = parent[head[v]];}}template<class F> void each_edge(int u, int v, F f) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) {if (u != v) f(label[u] + 1, label[v]);return;}f(label[head[v]], label[v]);v = parent[head[v]];}}int operator[](int u) {return label[u];};};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int N; cin >> N;vector<vector<int>> G(N);vector<vector<pair<int, ll>>> GW(N);rep(i, N - 1) {int a, b, c; cin >> a >> b >> c;G[a].push_back(b);G[b].push_back(a);GW[a].emplace_back(b, c);GW[b].emplace_back(a, c);}HLD hld(G);vector<ll> dep(N);int k = 0;auto dfs = [&](auto dfs, int u, int p) -> void {for (auto e : GW[u]) if (e.first != p) {dep[e.first] = dep[u] + e.second;dfs(dfs, e.first, u);}};dfs(dfs, 0, -1);int Q; cin >> Q;while (Q--) {int k; cin >> k;vector<int> a(k); rep(i, k) cin >> a[i];priority_queue<pair<int, int>> q;ll ans = 0;map<int, int> par;rep(i, k) {q.emplace(hld[a[i]], a[i]);par[a[i]] = -1;}while (q.size() >= 2) {int u = q.top().second; q.pop();int v = q.top().second;int w = hld.lca(u, v);if (u != w && (par[u] == -1 || dep[par[u]] < dep[w])) par[u] = w;if (v != w && (par[v] == -1 || dep[par[v]] < dep[w])) par[v] = w;if (!par.count(w)) {par[w] = -1;q.emplace(hld[w], w);}}for (auto kv : par) {if (kv.second != -1) {ans += dep[kv.first] - dep[kv.second];}}cout << ans << '\n';}}