結果
| 問題 | No.901 K-ary εxtrεεmε |
| コンテスト | |
| ユーザー |
 hidehic0
|
| 提出日時 | 2026-05-29 20:56:26 |
| 言語 | C++23(gnu拡張) (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 292 ms / 3,000 ms |
| コード長 | 7,186 bytes |
| 記録 | |
| コンパイル時間 | 4,573 ms |
| コンパイル使用メモリ | 366,600 KB |
| 実行使用メモリ | 50,432 KB |
| 最終ジャッジ日時 | 2026-05-29 20:56:48 |
| 合計ジャッジ時間 | 12,470 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge3_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
コンパイルメッセージ
/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp: In instantiation of 'LcaWithDoubling<T>::LcaWithDoubling(VC<std::vector<_Tp> >, T) [with T = long long int; VC<std::vector<_Tp> > = std::vector<std::vector<long long int, std::allocator<long long int> >, std::allocator<std::vector<long long int, std::allocator<long long int> > > >]':
/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/auxiliary_tree.hpp:11:50: required from 'AuxiliaryTree<T>::AuxiliaryTree(std::vector<std::vector<_Tp>, std::allocator<std::vector<_Tp> > >) [with T = long long int]'
test.cpp:26:26: required from here
/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp:13:58: warning: narrowing conversion of 'G.std::vector<std::vector<long long int, std::allocator<long long int> >, std::allocator<std::vector<long long int, std::allocator<long long int> > > >::size()' from 'std::vector<std::vector<long long int, std::allocator<long long int> >, std::allocator<std::vector<long long int, std::allocator<long long int> > > >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
ソースコード
#line 1 "test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/3407
#include <bits/stdc++.h>
using namespace std;
#line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp"
template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<
constexpr int MOD998 = 998244353;
#line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp"
// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
template <typename T> bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T> bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &in : v)
is >> in;
return is;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 == v.size() ? "" : " ");
}
return os;
}
// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
std::cout << t;
if (sizeof...(u))
std::cout << sep;
out(u...);
}
// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
std::cin >> t;
in(u...);
}
template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
T res = 1;
while (n) {
if (n % 2 != 0) {
res *= a;
res %= mod;
}
a *= a;
a %= mod;
n >>= 1;
}
return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }
template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
for (int i = 0; i < v.size(); i++)
v[i] = fn(v[i]);
}
#line 6 "test.cpp"
#line 3 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/auxiliary_tree.hpp"
#line 2 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp"
#line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp"
#line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp"
template <std::integral T> struct LcaWithDoubling {
VC<VC<T>> G, P;
VC<T> D;
T N, K;
LcaWithDoubling(VC<VC<T>> G, T st = 0) : G{G}, N{G.size()} {
assert(N > 0);
assert(st < N);
K = std::bit_width((unsigned)N);
P.resize(K, VC<T>(N, -1));
D.resize(N);
auto dfs = [&](const auto &self, T cur, T par, T d) -> void {
P[0][cur] = par;
D[cur] = d;
for (auto nxt : G[cur]) {
if (nxt == par)
continue;
self(self, nxt, cur, d + 1);
}
};
dfs(dfs, st, st, 0);
rep(b, K - 1) rep(i, N) P[b + 1][i] = P[b][P[b][i]];
}
T lca(T u, T v) {
if (D[u] < D[v])
std::swap(u, v);
rep(k, K) {
if ((D[u] - D[v]) >> k & 1) {
u = P[k][u];
}
}
if (u == v) {
return u;
}
rrep(k, K) {
if (P[k][u] != P[k][v]) {
u = P[k][u], v = P[k][v];
}
}
return P[0][u];
}
};
#line 5 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/auxiliary_tree.hpp"
template <std::integral T> struct AuxiliaryTree {
LcaWithDoubling<T> lca;
std::vector<int> order;
int n;
AuxiliaryTree(std::vector<std::vector<T>> G) : lca{G} {
n = G.size();
order.resize(n);
int cnt = 0;
auto dfs = [&](int cur, int par, const auto &self) -> void {
order[cur] = cnt++;
for (auto nxt : G[cur]) {
if (nxt == par)
continue;
self(nxt, cur, self);
}
};
dfs(0, -1, dfs);
}
/**
* @fn build
* @brief AuxiliaryTreeを構築します
* @param V 頂点のリスト 後で補助に使われた頂点も追加される
*/
T build(std::vector<T> &V, std::vector<std::vector<T>> &G) {
int m = V.size();
assert(n == G.size());
assert(m > 0);
std::ranges::sort(V, [&](int a, int b) { return order[a] < order[b]; });
std::vector<T> st = {V[0]};
for (int i = 0; i < m - 1; i++) {
T w = lca.lca(V[i], V[i + 1]);
if (w != V[i]) {
T last = st.back();
st.pop_back();
while (!st.empty() && lca.D[w] < lca.D[st.back()]) {
int tp = st.back();
st.pop_back();
G[tp].emplace_back(last);
last = tp;
}
if (st.empty() || st.back() != w) {
st.emplace_back(w), V.emplace_back(w);
G[w] = {last};
} else {
G[w].emplace_back(last);
}
}
st.emplace_back(V[i + 1]);
}
for (int i = 0; i < st.size() - 1; i++) {
G[st[i]].emplace_back(st[i + 1]);
}
return st[0];
}
};
/**
* @file tree/auxiliary_tree.hpp
* @brief AuxiliaryTree
* @auther hidehic0
* @date 2026-05-29
* verify: https://atcoder.jp/contests/abc340/submissions/76203724
*/
#line 8 "test.cpp"
int main() {
ll N;
in(N);
vi D(N, 0);
vvi VG(N);
vvpii G(N);
rep(_, N - 1) {
ll u, v, w;
in(u, v, w);
G[u].emplace_back(v, w), G[v].emplace_back(u, w);
VG[u].emplace_back(v), VG[v].emplace_back(u);
}
AuxiliaryTree<ll> AT(VG);
auto dfs = [&](ll cur, ll par, ll d, const auto &self) -> void {
D[cur] = d;
for (auto [nxt, w] : G[cur]) {
if (nxt == par)
continue;
self(nxt, cur, d + w, self);
}
};
dfs(0, -1, 0, dfs);
ll Q;
in(Q);
vvi AG(N);
while (Q--) {
ll K;
in(K);
vi X(K);
in(X);
ll root = AT.build(X, AG), res = 0;
auto dfs = [&](ll cur, const auto &self) -> void {
for (auto nxt : AG[cur]) {
res += D[nxt] - D[cur];
self(nxt, self);
}
};
dfs(root, dfs);
out(res);
for (auto x : X)
AG[x].clear();
}
}