結果

問題 No.901 K-ary εxtrεεmε
ユーザー pekempeypekempey
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0