CompetitiveProgrammingCpp
This documentation is automatically generated by online-judge-tools/verification-helper
Test/Graph/Tree/HeavyLightDecomposition_edge.test.cpp
- View this file on GitHub
- Last update: 2025-06-09 16:27:38+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_E
Depends on
- Library/Algebraic/Monoid.hpp
- Library/DataStructure/LazySegmentTree.hpp
- Library/Graph/Graph.hpp
- Library/Graph/Tree/HeavyLightDecomposition.hpp
Code
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_E"
#include <iostream>
// begin:tag includes
#include "./../../../Library/DataStructure/LazySegmentTree.hpp"
#include "./../../../Library/Graph/Graph.hpp"
#include "./../../../Library/Graph/Tree/HeavyLightDecomposition.hpp"
// end:tag includes
using ll = long long;
signed main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
ll n;
std::cin >> n;
auto size = n + n - 1;
auto tree = mtd::Graph<int, bool>(size);
ll add = n;
for (int f = 0; f < n; ++f) {
int k;
std::cin >> k;
for (int _ = 0; _ < k; ++_) {
int t;
std::cin >> t;
tree.addEdge(f, add);
tree.addEdge(t, add);
++add;
}
}
std::vector<std::pair<ll, ll>> v(n - 1, {0, 1});
auto segtree = mtd::LazySegmentTree<mtd::type::M_SUM, mtd::type::M_ADD,
mtd::type::OP_SUM_ADD>(n - 1, v);
// NOTE: 初期値が含まれる場合はID順に並び変える
// val[hld.getEdgeId(i + n)] = v[i];
auto hld = mtd::HeavyLightDecomposition(tree);
ll q;
std::cin >> q;
for (int _ = 0; _ < q; ++_) {
ll k;
std::cin >> k;
if (k == 0) {
ll v, w;
std::cin >> v >> w;
for (const auto& [l, r] : hld.rangeEdge(0, v)) {
segtree.update(l, r, w);
}
} else {
ll u;
std::cin >> u;
ll ans = 0;
for (const auto& [l, r] : hld.rangeEdge(0, u)) {
ans += segtree.query(l, r).first;
}
std::cout << ans << std::endl;
}
}
}#line 1 "Test/Graph/Tree/HeavyLightDecomposition_edge.test.cpp"
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_E"
#include <iostream>
// begin:tag includes
#line 2 "Library/DataStructure/LazySegmentTree.hpp"
#include <deque>
#line 5 "Library/DataStructure/LazySegmentTree.hpp"
#include <utility>
#include <vector>
#line 2 "Library/Algebraic/Monoid.hpp"
#line 4 "Library/Algebraic/Monoid.hpp"
namespace mtd {
template <class S, // set
S element, // identity element
class op // binary operation
>
requires std::is_invocable_r_v<S, op, S, S>
struct Monoid {
using value_type = S;
constexpr static S _element = element;
using op_type = op;
S m_val;
constexpr Monoid(S val) : m_val(val) {}
constexpr Monoid() : Monoid(element) {}
constexpr Monoid binaryOperation(const Monoid& m2) const {
return op()(m_val, m2.m_val);
}
friend std::ostream& operator<<(std::ostream& os,
const Monoid<S, element, op>& m) {
return os << m.m_val;
}
};
namespace __detail {
template <typename T, template <typename, auto, typename> typename S>
concept is_monoid_specialization_of = requires {
typename std::enable_if_t<std::is_same_v<
T, S<typename T::value_type, T::_element, typename T::op_type>>>;
};
} // namespace __detail
template <typename M>
concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;
} // namespace mtd
#line 9 "Library/DataStructure/LazySegmentTree.hpp"
namespace mtd {
template <monoid Monoid, monoid MonoidOp, class op>
class LazySegmentTree {
private:
const int m_size;
std::vector<Monoid> m_node;
std::vector<MonoidOp> m_lazy;
using S = decltype(Monoid().m_val);
constexpr int calcSize(int n) const {
int size = 1;
while (size < n) { size <<= 1; }
return size;
}
constexpr auto _lazy_update(int i, const MonoidOp& val) {
if (i >= (m_size << 1) - 1) { return; }
m_lazy[i] = m_lazy[i].binaryOperation(val);
}
constexpr auto _propagate(int i) {
m_node[i] = op()(m_node[i], m_lazy[i]);
_lazy_update((i << 1) + 1, m_lazy[i]);
_lazy_update((i << 1) + 2, m_lazy[i]);
m_lazy[i] = MonoidOp();
}
constexpr auto _update(int l, int r, int k, int nl, int nr,
const MonoidOp& m) {
_propagate(k);
if (nr < l || r < nl) { return; }
if (l <= nl && nr <= r) {
_lazy_update(k, m);
_propagate(k);
return;
}
_update(l, r, (k << 1) + 1, nl, (nl + nr) >> 1, m);
_update(l, r, (k << 1) + 2, ((nl + nr) >> 1) + 1, nr, m);
m_node[k] = m_node[(k << 1) + 1].binaryOperation(m_node[(k << 1) + 2]);
}
constexpr auto _query(int l, int r, int k, int nl, int nr) {
_propagate(k);
if (nr < l || r < nl) { return Monoid(); }
if (l <= nl && nr <= r) { return m_node[k]; }
auto l_val = _query(l, r, (k << 1) + 1, nl, (nl + nr) >> 1);
auto r_val = _query(l, r, (k << 1) + 2, ((nl + nr) >> 1) + 1, nr);
return l_val.binaryOperation(r_val);
}
constexpr auto _construct(const std::vector<S>& vec) {
for (unsigned int i = 0; i < vec.size(); ++i) {
m_node[i + m_size - 1] = Monoid(vec[i]);
}
for (int i = m_size - 2; i >= 0; --i) {
m_node[i] =
m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1LL]);
}
}
public:
constexpr LazySegmentTree(int n)
: m_size(calcSize(n)),
m_node((m_size << 1) - 1),
m_lazy((m_size << 1) - 1) {}
constexpr LazySegmentTree(int n, const std::vector<S>& vec)
: LazySegmentTree(n) {
_construct(vec);
}
constexpr auto update(int l, int r, const MonoidOp& val) {
_update(l, r, 0, 0, m_size - 1, val);
}
constexpr auto query(int l, int r) {
return _query(l, r, 0, 0, m_size - 1).m_val;
}
/*
* f([l, r]) = true となる最大のr
* judge: (Monoid) -> bool
**/
template <class F>
constexpr auto max_right(int _l, const F& judge) {
if (!judge(Monoid())) {
throw std::runtime_error("SegmentTree.max_right.judge(e) must be true");
}
query(_l, m_size - 1);
auto l = std::max(_l, 0) + m_size;
auto r = 2 * m_size - 1;
auto lm = Monoid();
while (l <= r) {
if (l & 1) {
auto next = lm.binaryOperation(m_node[l - 1]);
if (!judge(next)) {
auto itr = l;
while (itr < m_size) {
auto litr = 2 * itr;
auto ritr = 2 * itr + 1;
_propagate(itr - 1);
_propagate(litr - 1);
auto lval = lm.binaryOperation(m_node[litr - 1]);
if (!judge(lval)) {
itr = litr;
} else {
itr = ritr;
std::swap(lm, lval);
}
}
return itr - m_size - 1;
}
std::swap(lm, next);
++l;
}
l >>= 1, r >>= 1;
}
return m_size - 1;
}
/*
* f([l, r]) = true となる最小のl
* judge: (Monoid) -> bool
**/
template <class F>
constexpr auto min_left(int _r, const F& judge) {
if (!judge(Monoid())) {
throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");
}
query(0, _r);
auto l = m_size;
auto r = std::min(_r, m_size - 1) + m_size;
auto rm = Monoid();
while (l <= r) {
if (l & 1) { ++l; }
if (!(r & 1) || (_r == m_size - 1 && r == 1)) {
auto next = m_node[r - 1].binaryOperation(rm);
if (!judge(next)) {
auto itr = r;
while (itr < m_size) {
auto litr = 2 * itr;
auto ritr = 2 * itr + 1;
_propagate(itr - 1);
_propagate(ritr - 1);
auto rval = m_node[ritr - 1].binaryOperation(rm);
if (!judge(rval)) {
itr = ritr;
} else {
itr = litr;
std::swap(rm, rval);
}
}
return itr - m_size + 1;
}
std::swap(rm, next);
--r;
}
l >>= 1, r >>= 1;
}
return 0;
}
constexpr auto debug() {
for (int i = 0; i < (m_size << 1) - 1; ++i) { _propagate(i); }
for (int i = 0; i < m_size; ++i) {
std::cout << m_node[m_size + i - 1] << " ";
}
std::cout << std::endl;
}
};
namespace type {
/* 各種頻出サンプル */
using P = std::pair<long long, long long>;
constexpr long long update_element = -1e18;
/*---- 要素 ----*/
using M_SUM = Monoid<P, P{0, 0}, decltype([](const P& a, const P& b) {
return P{a.first + b.first, a.second + b.second};
})>;
using M_MIN = Monoid<long long, static_cast<long long>(1e18),
decltype([](long long a, long long b) {
return std::min(a, b);
})>;
using M_MAX = Monoid<long long, static_cast<long long>(-1e18),
decltype([](long long a, long long b) {
return std::max(a, b);
})>;
/*---- 作用素 ----*/
using M_UP = Monoid<long long, update_element,
decltype([](long long a, long long b) {
if (b == update_element) { return a; }
return b;
})>;
using M_ADD =
Monoid<long long, static_cast<long long>(0),
decltype([](long long a, long long b) { return a + b; })>;
/*---- 作用 ----*/
using OP_SUM_UP = decltype([](const M_SUM& m, const M_UP& m2) {
if (m2.m_val == update_element) { return m; }
return M_SUM(P{m.m_val.second * m2.m_val, m.m_val.second});
});
using OP_MIN_UP = decltype([](const M_MIN& m, const M_UP& m2) {
if (m2.m_val == update_element) { return m; }
return M_MIN(m2.m_val);
});
using OP_MAX_UP = decltype([](const M_MAX& m, const M_UP& m2) {
if (m2.m_val == update_element) { return m; }
return M_MAX(m2.m_val);
});
using OP_SUM_ADD = decltype([](const M_SUM& m, const M_ADD& m2) {
return M_SUM(
P{m.m_val.first + m.m_val.second * m2.m_val, m.m_val.second});
});
using OP_MIN_ADD = decltype([](const M_MIN& m, const M_ADD& m2) {
return M_MIN{m.m_val + m2.m_val};
});
using OP_MAX_ADD = decltype([](const M_MAX& m, const M_ADD& m2) {
return M_MAX{m.m_val + m2.m_val};
});
} // namespace type
} // namespace mtd
#line 4 "Library/Graph/Graph.hpp"
#include <ranges>
#include <tuple>
#line 7 "Library/Graph/Graph.hpp"
namespace mtd {
template <class Node = long long, class Cost = long long>
class Graph {
using Edge = std::pair<Node, Cost>;
using Edges = std::vector<Edge>;
const int m_n;
std::vector<Edges> m_graph;
public:
Graph(int n) : m_n(n), m_graph(n) {}
Graph(const std::vector<Edges>& edges)
: m_n(edges.size()), m_graph(edges) {}
Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
bool is_arc = false, bool is_index1 = true)
: Graph<Node, Cost>(n) {
for (auto [u, v] : edges) {
u -= is_index1;
v -= is_index1;
if (is_arc) {
addArc(u, v);
} else {
addEdge(u, v);
}
}
}
Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
bool is_arc = false, bool is_index1 = true)
: Graph<Node, Cost>(n) {
for (auto [u, v, c] : edges) {
u -= is_index1;
v -= is_index1;
if (is_arc) {
addArc(u, v, c);
} else {
addEdge(u, v, c);
}
}
}
auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
addArc(f, t, c);
addArc(t, f, c);
}
auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
m_graph[f].emplace_back(t, c);
}
auto getEdges(const Node& from) const {
class EdgesRange {
const typename Edges::const_iterator b, e;
public:
EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
auto begin() const { return b; }
auto end() const { return e; }
};
return EdgesRange(m_graph[from]);
}
auto getEdges() const {
std::deque<std::tuple<Node, Node, Cost>> edges;
for (Node from : std::views::iota(0, m_n)) {
for (const auto& [to, c] : getEdges(from)) {
edges.emplace_back(from, to, c);
}
}
return edges;
}
auto getEdgesExcludeCost() const {
std::deque<std::pair<Node, Node>> edges;
for (Node from : std::views::iota(0, m_n)) {
for (const auto& [to, _] : getEdges(from)) {
edges.emplace_back(from, to);
}
}
return edges;
}
auto reverse() const {
auto rev = Graph<Node, Cost>(m_n);
for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
return rev;
}
auto size() const { return m_n; };
auto debug(bool directed = false) const {
for (const auto& [f, t, c] : getEdges()) {
if (f < t || directed) {
std::cout << f << " -> " << t << ": " << c << std::endl;
}
}
}
};
} // namespace mtd
#line 2 "Library/Graph/Tree/HeavyLightDecomposition.hpp"
#include <queue>
#include <stack>
#include <unordered_map>
#line 8 "Library/Graph/Tree/HeavyLightDecomposition.hpp"
namespace mtd {
template <class Node, class Cost>
class HeavyLightDecomposition {
using GraphOrderd = std::unordered_map<Node, std::deque<Node>>;
const Node m_n;
const std::vector<Node> m_size;
const GraphOrderd m_tree;
const std::vector<Node> m_height;
const std::vector<std::pair<Node, Node>> m_root_par;
const std::vector<Node> m_ids;
const std::vector<Node> m_order;
const std::vector<Node> m_edge_ids;
static auto constructGraph(const Graph<Node, Cost>& tree) {
auto n = tree.size();
std::deque<std::pair<Node, Node>> order;
std::vector<Node> used(n);
std::stack<std::pair<Node, Node>> stk;
stk.emplace(0, -1);
used[0] = true;
while (!stk.empty()) {
auto [f, p] = stk.top();
order.emplace_front(f, p);
stk.pop();
for (const auto& [t, _] : tree.getEdges(f)) {
if (used[t]) {
continue;
;
}
used[t] = true;
stk.emplace(t, f);
}
}
std::vector<Node> size(n, 1);
GraphOrderd hld_tree;
for (const auto& [f, p] : order) {
Node size_sum = 1;
Node size_max = 0;
std::deque<Node> to_list;
for (const auto& [t, _] : tree.getEdges(f)) {
if (t == p) { continue; }
if (size[t] > size_max) {
size_max = size[t];
to_list.emplace_back(t);
} else {
to_list.emplace_front(t);
}
size_sum += size[t];
}
if (!to_list.empty()) { hld_tree.emplace(f, to_list); }
size[f] = size_sum;
}
return hld_tree;
}
static auto constructSize(const Graph<Node, Cost>& tree) {
auto n = tree.size();
std::deque<std::pair<Node, Node>> order;
std::vector<Node> used(n);
std::stack<std::pair<Node, Node>> stk;
stk.emplace(0, -1);
used[0] = true;
while (!stk.empty()) {
auto [f, p] = stk.top();
order.emplace_front(f, p);
stk.pop();
for (const auto& [t, _] : tree.getEdges(f)) {
if (used[t]) {
continue;
;
}
used[t] = true;
stk.emplace(t, f);
}
}
std::vector<Node> size(n, 1);
for (const auto& [f, p] : order) {
Node size_sum = 1;
for (const auto& [t, _] : tree.getEdges(f)) {
if (t == p) { continue; }
size_sum += size[t];
}
size[f] = size_sum;
}
return size;
}
static auto constructRootPar(Node n, const GraphOrderd& tree) {
std::vector<std::pair<Node, Node>> root_par(n);
std::stack<std::tuple<Node, Node, Node>> stk;
stk.emplace(0, 0, -1);
while (!stk.empty()) {
auto [f, root, par] = stk.top();
stk.pop();
if (tree.find(f) == tree.end()) {
root_par[f] = {root, par};
continue;
}
auto itr = tree.at(f).rbegin();
stk.emplace(*itr, root, par);
root_par[f] = {root, par};
for (++itr; itr != tree.at(f).rend(); ++itr) {
stk.emplace(*itr, *itr, f);
}
}
return root_par;
}
static auto constructHeight(Node n, const GraphOrderd& tree) {
std::vector<Node> height(n);
std::queue<Node> q;
q.emplace(0);
while (!q.empty()) {
auto f = q.front();
q.pop();
if (tree.find(f) == tree.end()) { continue; }
for (const auto& t : tree.at(f)) {
height[t] = height[f] + 1;
q.emplace(t);
}
}
return height;
}
auto constructIds() const {
std::vector<Node> ids(m_n);
Node val = 0;
std::stack<Node> stk;
stk.emplace(0);
while (!stk.empty()) {
auto f = stk.top();
stk.pop();
ids[f] = val;
++val;
if (m_tree.find(f) == m_tree.end()) { continue; }
for (const auto& t : m_tree.at(f)) { stk.emplace(t); }
}
return ids;
}
auto constructOrder() const {
std::vector<Node> order(m_n);
for (int i = 0; i < m_n; ++i) { order[m_ids[i]] = i; }
return order;
}
/*
* 辺をnodeとして拡張した場合の辺nodeだけIDを振る
* (1) - (2)
* (1) - (e) - (2)
* [-1, -1, 0]
*/
auto constructEdgeIds() const {
Node edge_size = (m_n >> 1);
std::vector<Node> edge_ids(m_n, -1);
Node val = 0;
std::stack<Node> stk;
stk.emplace(0);
while (!stk.empty()) {
auto f = stk.top();
stk.pop();
if (f > edge_size) {
edge_ids[f] = val;
++val;
}
if (m_tree.find(f) == m_tree.end()) { continue; }
for (const auto& t : m_tree.at(f)) { stk.emplace(t); }
}
return edge_ids;
}
public:
HeavyLightDecomposition(const Graph<Node, Cost>& tree)
: m_n(tree.size()),
m_size(constructSize(tree)),
m_tree(constructGraph(tree)),
m_root_par(constructRootPar(m_n, m_tree)),
m_height(constructHeight(m_n, m_tree)),
m_ids(constructIds()),
m_order(constructOrder()),
m_edge_ids(constructEdgeIds()) {}
auto getId(Node i) const { return m_ids[i]; }
auto getEdgeId(Node i) const { return m_edge_ids[i]; }
auto getOrder(Node i) const { return m_order[i]; }
auto lca(Node f, Node t) const {
do {
auto [fr, fp] = m_root_par[f];
auto [tr, tp] = m_root_par[t];
if (fr == tr) { break; }
auto fph = (fp > -1) ? m_height[fp] : -1;
auto tph = (tp > -1) ? m_height[tp] : -1;
if (fph < tph) {
t = tp;
} else {
f = fp;
}
} while (true);
return (m_height[f] < m_height[t]) ? f : t;
}
auto range(Node f, Node t) const {
std::deque<std::pair<Node, Node>> ret;
auto add = [&](Node from, Node to) {
auto l = std::min(m_ids[from], m_ids[to]);
auto r = std::max(m_ids[from], m_ids[to]);
ret.emplace_back(l, r);
};
do {
auto [fr, fp] = m_root_par[f];
auto [tr, tp] = m_root_par[t];
if (fr == tr) {
add(f, t);
break;
}
auto fph = (fp > -1) ? m_height[fp] : -1;
auto tph = (tp > -1) ? m_height[tp] : -1;
if (fph < tph) {
add(t, tr);
t = tp;
} else {
add(f, fr);
f = fp;
}
} while (true);
return ret;
}
auto rangeEdge(Node f, Node t) const {
Node edge_size = (m_n >> 1);
std::deque<std::pair<Node, Node>> ret;
auto add = [&](Node from, Node to) {
auto l = std::min(m_ids[from], m_ids[to]);
auto r = std::max(m_ids[from], m_ids[to]);
if (m_order[l] <= edge_size) { ++l; }
if (m_order[r] <= edge_size) { --r; }
if (l > r) { return; }
auto edge_l = m_edge_ids[m_order[l]];
auto edge_r = m_edge_ids[m_order[r]];
ret.emplace_back(edge_l, edge_r);
};
do {
auto [fr, fp] = m_root_par[f];
auto [tr, tp] = m_root_par[t];
if (fr == tr) {
add(f, t);
break;
}
auto fph = (fp > -1) ? m_height[fp] : -1;
auto tph = (tp > -1) ? m_height[tp] : -1;
if (fph < tph) {
add(t, tr);
t = tp;
} else {
add(f, fr);
f = fp;
}
} while (true);
return ret;
}
auto rangeSubTree(Node f) const {
return std::pair<Node, Node>{m_ids[f], m_ids[f] + m_size[f] - 1};
}
};
} // namespace mtd
#line 10 "Test/Graph/Tree/HeavyLightDecomposition_edge.test.cpp"
// end:tag includes
using ll = long long;
signed main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
ll n;
std::cin >> n;
auto size = n + n - 1;
auto tree = mtd::Graph<int, bool>(size);
ll add = n;
for (int f = 0; f < n; ++f) {
int k;
std::cin >> k;
for (int _ = 0; _ < k; ++_) {
int t;
std::cin >> t;
tree.addEdge(f, add);
tree.addEdge(t, add);
++add;
}
}
std::vector<std::pair<ll, ll>> v(n - 1, {0, 1});
auto segtree = mtd::LazySegmentTree<mtd::type::M_SUM, mtd::type::M_ADD,
mtd::type::OP_SUM_ADD>(n - 1, v);
// NOTE: 初期値が含まれる場合はID順に並び変える
// val[hld.getEdgeId(i + n)] = v[i];
auto hld = mtd::HeavyLightDecomposition(tree);
ll q;
std::cin >> q;
for (int _ = 0; _ < q; ++_) {
ll k;
std::cin >> k;
if (k == 0) {
ll v, w;
std::cin >> v >> w;
for (const auto& [l, r] : hld.rangeEdge(0, v)) {
segtree.update(l, r, w);
}
} else {
ll u;
std::cin >> u;
ll ans = 0;
for (const auto& [l, r] : hld.rangeEdge(0, u)) {
ans += segtree.query(l, r).first;
}
std::cout << ans << std::endl;
}
}
}