rcpl
This documentation is automatically generated by online-judge-tools/verification-helper
verify/graph/euler_tour.test.cpp
- View this file on GitHub
- Last update: 2024-08-06 14:48:44+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D
Depends on
- algebra/monoid_s/monoid_sum.hpp
- Segment Tree (セグメント木)
(data_structure/segment_tree.hpp)
- Euler Tour (オイラーツアー)
(graph/euler_tour.hpp)
- グラフテンプレート
(graph/graph_template.hpp)
- グラフ入力ライブラリ
(graph/read_graph.hpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D"
#include <iostream>
#include "graph/read_graph.hpp"
#include "graph/euler_tour.hpp"
#include "data_structure/segment_tree.hpp"
#include "algebra/monoid_s/monoid_sum.hpp"
int main() {
int N;
std::cin >> N;
Graph<int> g(N);
std::vector<int> id(N, -1);
for (int i = 0; i < N; i++) {
int K;
std::cin >> K;
for (int j = 0; j < K; j++) {
int c;
std::cin >> c;
id[c] = g.add_edge(i, c, 0);
}
}
EulerTour et(g);
SegmentTree<MonoidSum<long long>> seg(2 * N - 2);
int Q;
std::cin >> Q;
for (int q = 0; q < Q; q++) {
int type;
std::cin >> type;
if (type == 0) {
int v, w;
std::cin >> v >> w;
int eid = id[v];
seg.chset(et.esl[eid], w);
seg.chset(et.esr[eid], -w);
} else {
int u;
std::cin >> u;
std::cout << seg.prod(0, et.vsl[u]) << '\n';
}
}
return 0;
}#line 1 "verify/graph/euler_tour.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D"
#include <iostream>
#line 2 "graph/read_graph.hpp"
#line 2 "graph/graph_template.hpp"
#include <vector>
#include <cassert>
template <class T> struct Edge {
int from, to;
T cost;
int id;
Edge() = default;
Edge(const int from, const int to, const T cost = T(1), const int id = -1) : from(from), to(to), cost(cost), id(id) {}
friend bool operator<(const Edge<T>& a, const Edge<T>& b) { return a.cost < b.cost; }
friend std::ostream& operator<<(std::ostream& os, const Edge<T>& e) {
// output format: {id: cost(from, to) = cost}
return os << "{" << e.id << ": cost(" << e.from << ", " << e.to << ") = " << e.cost << "}";
}
};
template <class T> using Edges = std::vector<Edge<T>>;
template <class T> struct Graph {
struct EdgeIterators {
public:
using Iterator = typename std::vector<Edge<T>>::iterator;
EdgeIterators() = default;
EdgeIterators(const Iterator& begit, const Iterator& endit) : begit(begit), endit(endit) {}
Iterator begin() const { return begit; }
Iterator end() const { return endit; }
size_t size() const { return std::distance(begit, endit); }
Edge<T>& operator[](int i) const { return begit[i]; }
private:
Iterator begit, endit;
};
int n, m;
bool is_build, is_directed;
std::vector<Edge<T>> edges;
// CSR (Compressed Row Storage) 形式用
std::vector<int> start;
std::vector<Edge<T>> csr_edges;
Graph() = default;
Graph(const int n, const bool directed = false) : n(n), m(0), is_build(false), is_directed(directed), start(n + 1, 0) {}
// 辺を追加し, その辺が何番目に追加されたかを返す
int add_edge(const int from, const int to, const T cost = T(1), int id = -1) {
assert(!is_build);
assert(0 <= from and from < n);
assert(0 <= to and to < n);
if (id == -1) id = m;
edges.emplace_back(from, to, cost, id);
return m++;
}
// CSR 形式でグラフを構築
void build() {
assert(!is_build);
for (auto&& e : edges) {
start[e.from + 1]++;
if (!is_directed) start[e.to + 1]++;
}
for (int v = 0; v < n; v++) start[v + 1] += start[v];
auto counter = start;
csr_edges.resize(start.back() + 1);
for (auto&& e : edges) {
csr_edges[counter[e.from]++] = e;
if (!is_directed) csr_edges[counter[e.to]++] = Edge(e.to, e.from, e.cost, e.id);
}
is_build = true;
}
EdgeIterators operator[](int i) {
if (!is_build) build();
return EdgeIterators(csr_edges.begin() + start[i], csr_edges.begin() + start[i + 1]);
}
size_t size() const { return (size_t)(n); }
friend std::ostream& operator<<(std::ostream& os, Graph<T>& g) {
os << "[";
for (int i = 0; i < (int)(g.size()); i++) {
os << "[";
for (int j = 0; j < (int)(g[i].size()); j++) {
os << g[i][j];
if (j + 1 != (int)(g[i].size())) os << ", ";
}
os << "]";
if (i + 1 != (int)(g.size())) os << ", ";
}
return os << "]";
}
};
#line 4 "graph/read_graph.hpp"
template <class T> Graph<T> read_graph(const int n, const int m, const bool weight = false, const bool directed = false, const int offset = 1) {
Graph<T> g(n, directed);
for (int i = 0; i < m; i++) {
int a, b;
std::cin >> a >> b;
a -= offset, b -= offset;
T c = 1;
if (weight) std::cin >> c;
g.add_edge(a, b, c);
}
g.build();
return g;
}
template <class T> Graph<T> read_parent(const int n, const bool weight = false, const bool directed = false, const int offset = 1) {
Graph<T> g(n, directed);
for (int i = 1; i < n; i++) {
int p;
std::cin >> p;
p -= offset;
T c = 1;
if (weight) std::cin >> c;
g.add_edge(p, i, c);
}
g.build();
return g;
}
#line 2 "graph/euler_tour.hpp"
#line 4 "graph/euler_tour.hpp"
#include <tuple>
// Euler Tour
// O(n + m)
// 辺と頂点のうち, 変化させるものを要素と見て, そうでないもので要素を区切ると考えると良い
template <class T> struct EulerTour {
int n;
std::vector<int> vertices; // DFS で訪問する頂点の番号を並べたもの, 2 * n - 1 要素
std::vector<int> edges; // DFS で通る辺の番号を並べたもの, 2 * n - 2 要素
std::vector<int> dir; // DFS で通る辺の向きが 0 = 子供方向, 1 = 親方向
std::vector<int> vsl; // vsl[v]: vertices[i] = v となる i の最小値
std::vector<int> vsr; // vsr[v]: vertices[i] = v となる i の最大値
std::vector<int> esl; // esl[e]: edges[i] = e かつ dir[i] = 0 となる i
std::vector<int> esr; // esr[e]: edges[i] = e かつ dir[i] = 1 となる i
EulerTour(Graph<T>& g, const int root = 0) : n((int)(g.size())), vsl(n, 2 * n - 1), vsr(n, -1), esl(n - 1, -1), esr(n - 1, -1) {
vertices.reserve(2 * n - 1);
edges.reserve(2 * n - 2);
dir.reserve(2 * n - 2);
auto dfs = [&](auto f, int cur, int par) -> void {
for (auto&& e : g[cur]) {
if (e.to == par) continue;
// 頂点を追加
vertices.emplace_back(cur);
// 子供方向の辺を追加
edges.emplace_back(e.id);
dir.emplace_back(0);
// DFS
f(f, e.to, cur);
// 親方向の辺を追加
edges.emplace_back(e.id);
dir.emplace_back(1);
}
// 頂点を追加
vertices.emplace_back(cur);
};
dfs(dfs, root, -1);
for (int i = 2 * n - 2; i >= 0; i--) vsl[vertices[i]] = i;
for (int i = 0; i < 2 * n - 1; i++) vsr[vertices[i]] = i;
for (int i = 0; i < 2 * n - 2; i++) (dir[i] == 0 ? esl[edges[i]] : esr[edges[i]]) = i;
}
};
#line 4 "data_structure/segment_tree.hpp"
template <class MS> struct SegmentTree {
public:
using S = typename MS::S;
SegmentTree() : SegmentTree(0) {}
SegmentTree(int n) : SegmentTree(std::vector<S>(n, MS::e())) {}
SegmentTree(const std::vector<S>& v) : n((int)(v.size())) {
log = 0;
while ((1U << log) < (unsigned int)(n)) log++;
size = 1 << log;
d = std::vector<S>(size << 1, MS::e());
for (int i = 0; i < n; i++) d[i + size] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, const S& x) {
assert(0 <= p and p < n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
void chset(int p, const S& x) {
assert(0 <= p and p < n);
p += size;
d[p] = MS::op(d[p], x);
for (int i = 1; i <= log; i++) update(p >> i);
}
S operator[](int p) const {
assert(0 <= p and p < n);
return d[p + size];
}
S get(int p) const {
assert(0 <= p && p < n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
S sml = MS::e(), smr = MS::e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = MS::op(sml, d[l++]);
if (r & 1) smr = MS::op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return MS::op(sml, smr);
}
S all_prod() const { return d[1]; }
template <class G> int max_right(int l, G& g) const {
assert(0 <= l and l <= n);
assert(g(MS::e()));
if (l == n) return n;
l += size;
S sm = MS::e();
do {
while ((l & 1) == 0) l >>= 1;
if (!g(MS::op(sm, d[l]))) {
while (l < size) {
l <<= 1;
if (g(MS::op(sm, d[l]))) {
sm = MS::op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = MS::op(sm, d[l]);
l++;
} while ((l & -l) != l);
return n;
}
template <class G> int min_left(int r, G& g) const {
assert(0 <= r and r <= n);
assert(g(MS::e()));
if (r == 0) return 0;
r += size;
S sm = MS::e();
do {
r--;
while (r > 1 and (r & 1)) r >>= 1;
if (!g(MS::op(d[r], sm))) {
while (r < size) {
r = (r << 1) | 1;
if (g(MS::op(d[r], sm))) {
sm = MS::op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = MS::op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
std::vector<S> make_vector() {
std::vector<S> vec(n);
for (int i = 0; i < n; i++) vec[i] = get(i);
return vec;
}
private:
int n, log, size;
std::vector<S> d;
inline void update(int k) { d[k] = MS::op(d[k << 1], d[(k << 1) | 1]); }
};
#line 2 "algebra/monoid_s/monoid_sum.hpp"
// MS
template <class T> struct MonoidSum {
using S = T;
static constexpr S op(S a, S b) { return a + b; }
static constexpr S e() { return T(0); }
};
#line 9 "verify/graph/euler_tour.test.cpp"
int main() {
int N;
std::cin >> N;
Graph<int> g(N);
std::vector<int> id(N, -1);
for (int i = 0; i < N; i++) {
int K;
std::cin >> K;
for (int j = 0; j < K; j++) {
int c;
std::cin >> c;
id[c] = g.add_edge(i, c, 0);
}
}
EulerTour et(g);
SegmentTree<MonoidSum<long long>> seg(2 * N - 2);
int Q;
std::cin >> Q;
for (int q = 0; q < Q; q++) {
int type;
std::cin >> type;
if (type == 0) {
int v, w;
std::cin >> v >> w;
int eid = id[v];
seg.chset(et.esl[eid], w);
seg.chset(et.esr[eid], -w);
} else {
int u;
std::cin >> u;
std::cout << seg.prod(0, et.vsl[u]) << '\n';
}
}
return 0;
}