結果
| 問題 | No.901 K-ary εxtrεεmε |
| コンテスト | |
| ユーザー |
 leeh18
|
| 提出日時 | 2026-02-28 16:26:16 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 223 ms / 3,000 ms |
| コード長 | 6,290 bytes |
| 記録 | |
| コンパイル時間 | 5,420 ms |
| コンパイル使用メモリ | 368,544 KB |
| 実行使用メモリ | 28,416 KB |
| 最終ジャッジ日時 | 2026-02-28 16:26:29 |
| 合計ジャッジ時間 | 12,647 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
ソースコード
#include <bits/stdc++.h>
struct heavy_light_decomposition {
heavy_light_decomposition(const std::vector<std::vector<int>> &graph, int root)
: n_(int(graph.size())), timer_(0), graph_(graph), size_(n_, 1), depth_(n_), parent_(n_, -1), top_(n_), in_(n_),
out_(n_) {
assert(0 <= root && root < n_);
top_[root] = root;
dfs_size(root);
dfs_hld(root);
}
template <typename Function> void access_node(int u, Function f) const {
assert(0 <= u && u < n_);
f(in_[u]);
}
template <typename Function>
std::enable_if_t<std::is_same_v<std::invoke_result_t<Function, int, int>, void>, void>
access_path(int u, int v, bool include_lca, Function f) const {
assert(0 <= u && u < n_ && 0 <= v && v < n_);
while (top_[u] != top_[v]) {
if (depth_[top_[u]] < depth_[top_[v]]) {
std::swap(u, v);
}
f(in_[top_[u]], in_[u] + 1);
u = parent_[top_[u]];
}
if (depth_[u] > depth_[v]) {
std::swap(u, v);
}
if (include_lca) {
f(in_[u], in_[v] + 1);
} else {
f(in_[u] + 1, in_[v] + 1);
}
}
template <typename Function>
std::enable_if_t<std::is_same_v<std::invoke_result_t<Function, int, int, bool>, void>, void>
access_path(int u, int v, bool include_lca, Function f) const {
assert(0 <= u && u < n_ && 0 <= v && v < n_);
bool u_to_lca = true;
while (top_[u] != top_[v]) {
if (depth_[top_[u]] < depth_[top_[v]]) {
std::swap(u, v);
u_to_lca = !u_to_lca;
}
f(in_[top_[u]], in_[u] + 1, u_to_lca);
u = parent_[top_[u]];
}
if (depth_[u] > depth_[v]) {
std::swap(u, v);
} else {
u_to_lca = !u_to_lca;
}
if (include_lca) {
f(in_[u], in_[v] + 1, u_to_lca);
} else {
f(in_[u] + 1, in_[v] + 1, u_to_lca);
}
}
template <typename Function> void access_subtree(int u, bool include_root, Function f) const {
assert(0 <= u && u < n_);
if (include_root) {
f(in_[u], out_[u]);
} else {
f(in_[u] + 1, out_[u]);
}
}
int lca(int u, int v) const {
assert(0 <= u && u < n_ && 0 <= v && v < n_);
while (top_[u] != top_[v]) {
if (depth_[top_[u]] < depth_[top_[v]]) {
std::swap(u, v);
}
u = parent_[top_[u]];
}
if (depth_[u] > depth_[v]) {
std::swap(u, v);
}
return u;
}
int in(int u) const {
assert(0 <= u && u < n_);
return in_[u];
}
int out(int u) const {
assert(0 <= u && u < n_);
return out_[u];
}
int depth(int u) const {
assert(0 <= u && u < n_);
return depth_[u];
};
private:
void dfs_size(int u) {
for (auto &v : graph_[u]) {
if (v != parent_[u]) {
depth_[v] = depth_[u] + 1;
parent_[v] = u;
dfs_size(v);
size_[u] += size_[v];
if (size_[graph_[u][0]] < size_[v] || graph_[u][0] == parent_[u]) {
std::swap(graph_[u][0], v);
}
}
}
}
void dfs_hld(int u) {
in_[u] = timer_++;
for (auto v : graph_[u]) {
if (v != parent_[u]) {
top_[v] = (v == graph_[u][0] ? top_[u] : v);
dfs_hld(v);
}
}
out_[u] = timer_;
}
const int n_;
int timer_;
std::vector<std::vector<int>> graph_;
std::vector<int> size_, depth_, parent_, top_, in_, out_;
};
struct AuxiliaryTree {
AuxiliaryTree(const std::vector<std::vector<int>> &graph, int root) : hld_(graph, root) {}
std::vector<std::pair<int, int>> get(std::vector<int> x) const {
if (x.empty()) {
return {};
}
std::ranges::sort(x, {}, [&](int u) { return hld_.in(u); });
const auto m = int(x.size());
for (auto i = 1; i < m; i++) {
x.push_back(hld_.lca(x[i - 1], x[i]));
}
std::ranges::sort(x, {}, [&](int u) { return hld_.in(u); });
auto r = std::ranges::unique(x);
x.erase(r.begin(), r.end());
const auto n = int(x.size());
std::vector<int> st;
std::vector<std::pair<int, int>> dfs_order(n);
st.push_back(x[0]);
dfs_order[0] = {x[0], -1};
for (auto i = 1; i < n; ++i) {
auto v = x[i];
while (!st.empty()) {
auto u = st.back();
if (hld_.in(u) <= hld_.in(v) && hld_.in(v) < hld_.out(u)) {
break;
} else {
st.pop_back();
}
}
auto parent = st.back();
dfs_order[i] = {v, parent};
st.push_back(v);
}
return dfs_order;
}
const heavy_light_decomposition &hld() const { return hld_; }
private:
const heavy_light_decomposition hld_;
};
int main() {
using i64 = long long;
std::cin.tie(0)->sync_with_stdio(0);
int N;
std::cin >> N;
std::vector<std::vector<std::pair<int, i64>>> adj(N);
std::vector<std::vector<int>> g(N);
for (auto i = 0; i < N - 1; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
g[u].push_back(v);
g[v].push_back(u);
}
std::vector<i64> dist(N);
auto dfs = [&](auto &&self, int u, int p) -> void {
for (auto [v, w] : adj[u]) {
if (v != p) {
dist[v] = dist[u] + w;
self(self, v, u);
}
}
};
dfs(dfs, 0, 0);
AuxiliaryTree aux(g, 0);
int Q;
std::cin >> Q;
while (Q--) {
int k;
std::cin >> k;
std::vector<int> x(k);
std::copy_n(std::istream_iterator<int>(std::cin), k, x.begin());
i64 ans = 0;
for (auto [u, p] : aux.get(move(x)) | std::views::drop(1)) {
ans += dist[u] - dist[p];
}
std::cout << ans << '\n';
}
}