結果
| 問題 |
No.901 K-ary εxtrεεmε
|
| ユーザー |
 kuhaku
|
| 提出日時 | 2025-03-12 16:34:45 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 246 ms / 3,000 ms |
| コード長 | 30,807 bytes |
| コンパイル時間 | 6,221 ms |
| コンパイル使用メモリ | 357,088 KB |
| 実行使用メモリ | 23,964 KB |
| 最終ジャッジ日時 | 2025-03-12 16:35:01 |
| 合計ジャッジ時間 | 14,333 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
ソースコード
// competitive-verifier: PROBLEM
#include <iostream>
#include <vector>
/**
* @brief 重み付きグラフ
*
* @tparam T 辺の重みの型
*/
template <class T>
struct Graph {
private:
struct _edge {
constexpr _edge() : _from(), _to(), _weight() {}
constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {}
constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); }
constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
constexpr int from() const { return _from; }
constexpr int to() const { return _to; }
constexpr T weight() const { return _weight; }
private:
int _from, _to;
T _weight;
};
public:
using edge_type = typename Graph<T>::_edge;
Graph() : _size(), edges() {}
Graph(int v) : _size(v), edges(v) {}
const auto &operator[](int i) const { return edges[i]; }
auto &operator[](int i) { return edges[i]; }
const auto begin() const { return edges.begin(); }
auto begin() { return edges.begin(); }
const auto end() const { return edges.end(); }
auto end() { return edges.end(); }
constexpr int size() const { return _size; }
void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); }
void add_edge(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); }
void add_edges(int from, int to, T weight = T(1)) {
edges[from].emplace_back(from, to, weight);
edges[to].emplace_back(to, from, weight);
}
void input_edge(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
T weight;
std::cin >> from >> to >> weight;
add_edge(from - base, to - base, weight);
}
}
void input_edges(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
T weight;
std::cin >> from >> to >> weight;
add_edges(from - base, to - base, weight);
}
}
private:
int _size;
std::vector<std::vector<edge_type>> edges;
};
template <>
struct Graph<void> {
private:
struct _edge {
constexpr _edge() : _from(), _to() {}
constexpr _edge(int from, int to) : _from(from), _to(to) {}
constexpr int from() const { return _from; }
constexpr int to() const { return _to; }
constexpr int weight() const { return 1; }
constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); }
constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
private:
int _from, _to;
};
public:
using edge_type = typename Graph<void>::_edge;
Graph() : _size(), edges() {}
Graph(int v) : _size(v), edges(v) {}
const auto &operator[](int i) const { return edges[i]; }
auto &operator[](int i) { return edges[i]; }
const auto begin() const { return edges.begin(); }
auto begin() { return edges.begin(); }
const auto end() const { return edges.end(); }
auto end() { return edges.end(); }
constexpr int size() const { return _size; }
void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); }
void add_edge(int from, int to) { edges[from].emplace_back(from, to); }
void add_edges(int from, int to) {
edges[from].emplace_back(from, to);
edges[to].emplace_back(to, from);
}
void input_edge(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
add_edge(from - base, to - base);
}
}
void input_edges(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
add_edges(from - base, to - base);
}
}
private:
int _size;
std::vector<std::vector<edge_type>> edges;
};
#include <cassert>
namespace internal {
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
// @param n `1 <= n`
// @return same with std::bit::countl_zero
int countl_zero(unsigned int n) { return __builtin_clz(n); }
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) { return __builtin_ctz(n); }
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>
template <class T>
struct Add {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs + rhs;
}
};
template <class T>
struct Mul {
using value_type = T;
static constexpr T id() { return T(1); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs * rhs;
}
};
template <class T>
struct And {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs & rhs;
}
};
template <class T>
struct Or {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs | rhs;
}
};
template <class T>
struct Xor {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs ^ rhs;
}
};
template <class T>
struct Min {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }
template <class U>
static constexpr U f(T lhs, U rhs) {
return std::min((U)lhs, rhs);
}
};
template <class T>
struct Max {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::lowest(); }
static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
template <class U>
static constexpr U f(T lhs, U rhs) {
return std::max((U)lhs, rhs);
}
};
template <class T>
struct Gcd {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) {
return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs));
}
};
template <class T>
struct Lcm {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) {
return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs));
}
};
template <class T>
struct Update {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs == Update::id() ? rhs : lhs;
}
};
template <class T>
struct Affine {
using P = std::pair<T, T>;
using value_type = P;
static constexpr P id() { return P(1, 0); }
static constexpr P op(P lhs, P rhs) {
return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second};
}
};
template <class M>
struct Rev {
using T = typename M::value_type;
using value_type = T;
static constexpr T id() { return M::id(); }
static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};
/**
* @brief セグメント木
* @see https://noshi91.hatenablog.com/entry/2020/04/22/212649
*
* @tparam M モノイド
*/
template <class M>
struct segment_tree {
private:
using T = typename M::value_type;
struct _segment_tree_reference {
private:
segment_tree<M> &self;
int k;
public:
_segment_tree_reference(segment_tree<M> &self, int k) : self(self), k(k) {}
_segment_tree_reference &operator=(const T &x) {
self.set(k, x);
return *this;
}
_segment_tree_reference &operator=(T &&x) {
self.set(k, std::move(x));
return *this;
}
operator T() const { return self.get(k); }
};
public:
segment_tree() : segment_tree(0) {}
explicit segment_tree(int n, T e = M::id()) : segment_tree(std::vector<T>(n, e)) {}
template <class U>
explicit segment_tree(const std::vector<U> &v) : _n(v.size()) {
_size = internal::bit_ceil(_n);
_log = internal::countr_zero(_size);
data = std::vector<T>(_size << 1, M::id());
for (int i = 0; i < _n; ++i) data[_size + i] = T(v[i]);
for (int i = _size - 1; i >= 1; --i) update(i);
}
const T &operator[](int k) const { return data[k + _size]; }
_segment_tree_reference operator[](int k) { return _segment_tree_reference(*this, k); }
T at(int k) const { return data[k + _size]; }
T get(int k) const { return data[k + _size]; }
void set(int k, T val) {
assert(0 <= k && k < _n);
k += _size;
data[k] = val;
for (int i = 1; i <= _log; ++i) update(k >> i);
}
void reset(int k) { set(k, M::id()); }
T all_prod() const { return data[1]; }
T prod(int a, int b) const {
assert(0 <= a && b <= _n);
T l = M::id(), r = M::id();
for (a += _size, b += _size; a < b; a >>= 1, b >>= 1) {
if (a & 1) l = M::op(l, data[a++]);
if (b & 1) r = M::op(data[--b], r);
}
return M::op(l, r);
}
template <class F>
int max_right(F f) const {
return max_right(0, f);
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(M::id()));
if (l == _n) return _n;
l += _size;
T sm = M::id();
do {
while (l % 2 == 0) l >>= 1;
if (!f(M::op(sm, data[l]))) {
while (l < _size) {
l = (2 * l);
if (f(M::op(sm, data[l]))) {
sm = M::op(sm, data[l]);
l++;
}
}
return l - _size;
}
sm = M::op(sm, data[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <class F>
int min_left(F f) const {
return min_left(_n, f);
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(M::id()));
if (r == 0) return 0;
r += _size;
T sm = M::id();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(M::op(data[r], sm))) {
while (r < _size) {
r = (2 * r + 1);
if (f(M::op(data[r], sm))) {
sm = M::op(data[r], sm);
r--;
}
}
return r + 1 - _size;
}
sm = M::op(data[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, _size, _log;
std::vector<T> data;
void update(int k) { data[k] = M::op(data[2 * k], data[2 * k + 1]); }
};
#ifdef ATCODER
#pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2")
#endif
#pragma GCC optimize("Ofast,fast-math,unroll-all-loops")
#include <bits/stdc++.h>
#ifndef ATCODER
#pragma GCC target("sse4.2,avx2,bmi2")
#endif
template <class T, class U>
constexpr bool chmax(T &a, const U &b) {
return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
constexpr bool chmin(T &a, const U &b) {
return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr double EPS = 1e-7;
constexpr double PI = 3.14159265358979323846;
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
struct Sonic {
Sonic() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(20);
}
constexpr void operator()() const {}
} sonic;
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &i : v) is >> i;
return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it;
return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); }
void No(bool is_not_correct = true) { Yes(!is_not_correct); }
void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); }
void NO(bool is_not_correct = true) { YES(!is_not_correct); }
void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; }
void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); }
/// @brief オイラーツアー
struct euler_tour {
template <class T>
euler_tour(const Graph<T> &g, int r = 0) : euler_tour(g, g.size(), r) {}
std::pair<int, int> operator[](int i) const { return std::make_pair(ls[i], rs[i]); }
int size() const { return _size; }
int left(int i) const { return ls[i]; }
int right(int i) const { return rs[i]; }
int order(int i) const { return ord[i]; }
template <class F>
void query(int v, const F &f) const {
f(ls[v], rs[v]);
}
private:
int _size;
std::vector<int> ord, ls, rs;
template <class T>
euler_tour(const Graph<T> &g, int n, int r) : _size(n), ord(n), ls(n, -1), rs(n) {
int c = 0;
std::stack<int> st;
st.emplace(r);
while (!st.empty()) {
auto x = st.top();
st.pop();
if (x < 0) {
rs[~x] = c;
continue;
}
ls[x] = c;
ord[x] = c++;
rs[x] = c;
for (auto e : g[x]) {
if (ls[e.to()] != -1) continue;
st.emplace(~x);
st.emplace(e.to());
}
}
}
};
#include <bit>
/// @brief スパーステーブル
template <class M>
struct sparse_table {
private:
using T = typename M::value_type;
public:
sparse_table() = default;
sparse_table(const std::vector<T> &v) : _size(v.size()), data() {
int b = std::max(1, std::countr_zero(std::bit_ceil<unsigned>(_size)));
data.emplace_back(v);
for (int i = 1; i < b; ++i) data.emplace_back(_size + 1 - (1 << i));
for (int i = 1; i < b; ++i) {
for (int j = 0; j + (1 << i) <= _size; ++j) {
data[i][j] = M::op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
}
}
}
T prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _size);
if (l == r) return M::id();
if (l + 1 == r) return data[0][l];
int b = 31 - std::countl_zero<unsigned>(r - l - 1);
return M::op(data[b][l], data[b][r - (1 << b)]);
}
private:
int _size;
std::vector<std::vector<T>> data;
};
namespace internal {
template <class T, int N>
struct fixed_stack {
constexpr fixed_stack() : _size(), _data() {}
constexpr T top() const { return _data[_size - 1]; }
constexpr bool empty() const { return _size == 0; }
constexpr int size() const { return _size; }
constexpr void emplace(const T &e) { _data[_size++] = e; }
constexpr void emplace(T &&e) { _data[_size++] = e; }
constexpr void pop() { --_size; }
constexpr void clear() { _size = 0; }
private:
int _size;
std::array<T, N> _data;
};
} // namespace internal
/**
* @brief 線形 Sparse Table
*
* @tparam M
*/
template <class M>
struct linear_sparse_table {
private:
using T = M::value_type;
static constexpr int W = 64;
public:
linear_sparse_table() = default;
linear_sparse_table(const std::vector<T> &v) : _size(v.size()), data(v) {
int n = v.size();
int b = n / W;
internal::fixed_stack<int, W + 1> st;
std::vector<T> u(b);
word_data.resize(b + (n > b * W));
for (int i = 0; i < b; ++i) {
T m = M::id();
std::uint64_t bit = 0;
std::vector<std::uint64_t> bits(W);
for (int j = 0; j < W; ++j) {
m = M::op(m, v[i * W + j]);
while (!st.empty() && M::op(v[i * W + st.top()], v[i * W + j]) == v[i * W + j]) {
bit ^= std::uint64_t(1) << st.top();
st.pop();
}
bits[j] = bit;
bit |= std::uint64_t(1) << j;
st.emplace(j);
}
u[i] = m;
word_data[i] = bits;
st.clear();
}
if (n > b * W) {
std::uint64_t bit = 0;
std::vector<std::uint64_t> bits(n - b * W);
for (int j = 0; j < n - b * W; ++j) {
while (!st.empty() && M::op(v[b * W + st.top()], v[b * W + j]) == v[b * W + j]) {
bit ^= std::uint64_t(1) << st.top();
st.pop();
}
bits[j] = bit;
bit |= std::uint64_t(1) << j;
st.emplace(j);
}
word_data[b] = bits;
}
block_table = sparse_table<M>(u);
}
const T &operator[](int k) const { return data[k]; }
T prod(int l, int r) const {
assert(0 <= l && l < r && r <= _size);
int lb = (l + W - 1) / W, rb = r / W;
if (lb > rb) return word_prod(l, r);
T res = (lb == rb ? M::id() : block_table.prod(lb, rb));
if (l < lb * W) res = M::op(res, word_prod(l, lb * W));
if (rb * W < r) res = M::op(res, word_prod(rb * W, r));
return res;
}
private:
int _size;
std::vector<T> data;
sparse_table<M> block_table;
std::vector<std::vector<std::uint64_t>> word_data;
T word_prod(int l, int r) const {
if (l == r) return M::id();
int b = l / W;
int lw = l - b * W, rw = r - b * W;
if ((word_data[b][rw - 1] >> lw) == 0ul) return data[r - 1];
return data[l + std::countr_zero(word_data[b][rw - 1] >> lw)];
}
};
struct linear_lca {
private:
struct S {
int depth, index;
bool operator<(const S &rhs) const { return depth < rhs.depth; }
bool operator==(const S &rhs) const = default;
};
struct M {
using value_type = S;
static constexpr S id() { return S{std::numeric_limits<int>::max(), -1}; }
static constexpr S op(const S &lhs, const S &rhs) { return std::min(lhs, rhs); }
};
public:
template <class T>
linear_lca(const Graph<T> &g, int r = 0) : ord(g.size(), -1), lst() {
std::vector<S> v;
std::stack<std::pair<int, int>> st;
st.emplace(r, 0);
while (!st.empty()) {
auto [x, d] = st.top();
st.pop();
if (x < 0) {
v.emplace_back(d, ~x);
continue;
}
ord[x] = v.size();
v.emplace_back(d, x);
for (auto e : g[x]) {
if (ord[e.to()] != -1) continue;
st.emplace(~x, d);
st.emplace(e.to(), d + 1);
}
}
lst = linear_sparse_table<M>(v);
}
int operator()(int u, int v) const { return lca(u, v); }
int lca(int u, int v) const {
auto [l, r] = std::minmax(ord[u], ord[v]);
return lst.prod(l, r + 1).index;
}
private:
std::vector<int> ord;
linear_sparse_table<M> lst;
};
struct auxiliary_tree : public Graph<void> {
auxiliary_tree(const std::vector<int> &_ord, const std::vector<int> &_par,
const std::vector<bool> &_f)
: Graph::Graph(_par.size()), ord(_ord), f(_f) {
int n = _par.size();
for (int i = 0; i < n; ++i) {
if (_par[i] != -1) add_edges(_par[i], i);
}
}
int vertex(int x) const { return ord[x]; }
bool contains(int x) const { return f[x]; }
private:
std::vector<int> ord;
std::vector<bool> f;
};
struct auxiliary_tree_builder {
template <class T>
auxiliary_tree_builder(const Graph<T> &g, int r = 0) : lca(g, r), et(g, r) {}
auxiliary_tree build(std::vector<int> v) {
std::sort(v.begin(), v.end(), [&](int x, int y) { return et.order(x) < et.order(y); });
v.erase(std::unique(v.begin(), v.end()), v.end());
std::vector<int> ord = v;
int k = ord.size();
for (int i = 0; i < k - 1; ++i) ord.emplace_back(lca(ord[i], ord[i + 1]));
std::sort(ord.begin(), ord.end(), [&](int x, int y) { return et.order(x) < et.order(y); });
ord.erase(std::unique(ord.begin(), ord.end()), ord.end());
int m = ord.size();
std::vector<int> par(m);
std::stack<int> st;
for (int i = 0; i < m; ++i) {
while (!st.empty() && et.right(ord[st.top()]) <= et.left(ord[i])) st.pop();
par[i] = (st.empty() ? -1 : st.top());
st.emplace(i);
}
std::vector<bool> f(m);
int x = 0;
for (int i = 0; i < m; ++i) {
if (x < k && ord[i] == v[x]) {
f[i] = true;
++x;
}
}
return auxiliary_tree{ord, par, f};
}
private:
linear_lca lca;
euler_tour et;
};
namespace internal {
struct graph_csr {
private:
struct edge_list {
using const_iterator = std::vector<int>::const_iterator;
edge_list(const graph_csr &g, int v) : g(g), v(v) {}
const_iterator begin() const { return std::next(g.elist.begin(), g.start[v]); }
const_iterator end() const { return std::next(g.elist.begin(), g.start[v + 1]); }
private:
const graph_csr &g;
int v;
};
public:
graph_csr(int n) : _size(n), edges(), start(n + 1) {}
edge_list operator[](int i) const { return edge_list(*this, i); }
constexpr int size() const { return _size; }
void build() {
for (auto [u, v] : edges) ++start[u + 1];
for (int i = 0; i < _size; ++i) start[i + 1] += start[i];
auto counter = start;
elist = std::vector<int>(edges.size());
for (auto [u, v] : edges) elist[counter[u]++] = v;
}
void add_edge(int u, int v) { edges.emplace_back(u, v); }
void add_edges(int u, int v) {
edges.emplace_back(u, v);
edges.emplace_back(v, u);
}
void input_edge(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
add_edge(from - base, to - base);
}
build();
}
void input_edges(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
add_edges(from - base, to - base);
}
build();
}
int _size;
std::vector<std::pair<int, int>> edges;
std::vector<int> elist;
std::vector<int> start;
};
} // namespace internal
/**
* @brief HL分解
* @see https://beet-aizu.github.io/library/tree/heavylightdecomposition.cpp
*/
struct heavy_light_decomposition {
heavy_light_decomposition() = default;
template <class T>
heavy_light_decomposition(const Graph<T> &g, int r = 0) : heavy_light_decomposition(g.size()) {
std::vector<int> heavy_path(_size, -1), sub_size(_size, 1);
std::stack<int> st;
st.emplace(r);
int pos = 0;
while (!st.empty()) {
int v = st.top();
st.pop();
vid[pos++] = v;
for (auto &e : g[v]) {
int u = e.to();
if (u == par[v]) continue;
par[u] = v, dep[u] = dep[v] + 1, st.emplace(u);
}
}
for (int i = _size - 1; i >= 0; --i) {
int v = vid[i];
int max_sub = 0;
for (auto &e : g[v]) {
int u = e.to();
if (u == par[v]) continue;
sub_size[v] += sub_size[u];
if (max_sub < sub_size[u]) max_sub = sub_size[u], heavy_path[v] = u;
}
}
nxt[r] = r;
pos = 0;
st.emplace(r);
while (!st.empty()) {
int v = st.top();
st.pop();
vid[v] = pos++;
inv[vid[v]] = v;
int hp = heavy_path[v];
for (auto &e : g[v]) {
int u = e.to();
if (u == par[v] || u == hp) continue;
nxt[u] = u, st.emplace(u);
}
if (hp != -1) nxt[hp] = nxt[v], st.emplace(hp);
}
}
heavy_light_decomposition(const internal::graph_csr &g, int r = 0)
: heavy_light_decomposition(g.size()) {
std::vector<int> heavy_path(_size, -1), sub_size(_size, 1);
std::stack<int> st;
st.emplace(r);
int pos = 0;
while (!st.empty()) {
int v = st.top();
st.pop();
vid[pos++] = v;
for (int u : g[v]) {
if (u == par[v]) continue;
par[u] = v, dep[u] = dep[v] + 1, st.emplace(u);
}
}
for (int i = _size - 1; i >= 0; --i) {
int v = vid[i];
int max_sub = 0;
for (int u : g[v]) {
if (u == par[v]) continue;
sub_size[v] += sub_size[u];
if (max_sub < sub_size[u]) max_sub = sub_size[u], heavy_path[v] = u;
}
}
nxt[r] = r;
pos = 0;
st.emplace(r);
while (!st.empty()) {
int v = st.top();
st.pop();
vid[v] = pos++;
inv[vid[v]] = v;
int hp = heavy_path[v];
for (int u : g[v]) {
if (u == par[v] || u == hp) continue;
nxt[u] = u, st.emplace(u);
}
if (hp != -1) nxt[hp] = nxt[v], st.emplace(hp);
}
}
constexpr int size() const { return _size; }
int get(int v) const { return vid[v]; }
int get_parent(int v) const { return par[v]; }
int get_depth(int v) const { return dep[v]; }
int dist(int u, int v) const {
int d = 0;
while (true) {
if (vid[u] > vid[v]) std::swap(u, v);
if (nxt[u] == nxt[v]) return d + vid[v] - vid[u];
d += vid[v] - vid[nxt[v]] + 1;
v = par[nxt[v]];
}
}
int jump(int u, int v, int k) const {
int d = dist(u, v);
if (d < k) return -1;
int l = lca(u, v);
if (dist(u, l) >= k) return la(u, k);
else return la(v, d - k);
}
int la(int v, int k) const {
while (true) {
int u = nxt[v];
if (vid[v] - k >= vid[u]) return inv[vid[v] - k];
k -= vid[v] - vid[u] + 1;
v = par[u];
}
}
int lca(int u, int v) const {
while (true) {
if (vid[u] > vid[v]) std::swap(u, v);
if (nxt[u] == nxt[v]) return u;
v = par[nxt[v]];
}
}
template <class F>
void for_each(int u, int v, const F &f) const {
while (true) {
if (vid[u] > vid[v]) std::swap(u, v);
f(std::max(vid[nxt[v]], vid[u]), vid[v] + 1);
if (nxt[u] != nxt[v]) v = par[nxt[v]];
else break;
}
}
template <class F>
void for_each_edge(int u, int v, const F &f) const {
while (true) {
if (vid[u] > vid[v]) std::swap(u, v);
if (nxt[u] != nxt[v]) {
f(vid[nxt[v]], vid[v] + 1);
v = par[nxt[v]];
} else {
if (u != v) f(vid[u] + 1, vid[v] + 1);
break;
}
}
}
private:
int _size;
std::vector<int> vid, nxt, par, dep, inv;
heavy_light_decomposition(int n) : _size(n), vid(n, -1), nxt(n), par(n, -1), dep(n), inv(n) {}
};
int main(void) {
int n;
cin >> n;
Graph<ll> g(n);
g.input_edges(n - 1, 0);
heavy_light_decomposition hld(g);
segment_tree<Add<ll>> st(n);
auto f = [&](auto self, int x, int p) -> void {
for (auto e : g[x]) {
if (e.to() == p)
continue;
st.set(hld.get(e.to()), e.weight());
self(self, e.to(), x);
}
};
f(f, 0, -1);
auxiliary_tree_builder at(g);
int q;
cin >> q;
while (q--) {
int k;
cin >> k;
vector<int> x(k);
cin >> x;
auto tr = at.build(x);
ll ans = 0;
auto g = [&](int x, int y) {
ans += st.prod(x, y);
};
auto dfs = [&](auto self, int v, int p) -> void {
for (auto e : tr[v]) {
if (e.to() == p)
continue;
hld.for_each_edge(tr.vertex(v), tr.vertex(e.to()), g);
self(self, e.to(), v);
}
};
dfs(dfs, 0, -1);
co(ans);
}
return 0;
}