test/EulerTourForEdge.test.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:30:27+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_D

Depends on

• DataStructure/BinaryIndexedTree.cpp
• Graph/EulerTourForEdge.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_D"
#include "./../Graph/EulerTourForEdge.cpp"
#include "./../DataStructure/BinaryIndexedTree.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for (vector<int>& v : g) {
		int k;
		cin >> k;
		v.resize(k);
		for (int& j : v) {
			cin >> j;
		}
	}

	EulerTourForEdge euler(g);
	euler.build();

	BinaryIndexedTree<long long> bit(euler.size());
	int q;
	cin >> q;
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int v;
			long long w;
			cin >> v >> w;
			bit.add(euler.l(v), +w);
			bit.add(euler.r(v), -w);
		} else if (com == 1) {
			int v;
			cin >> v;
			cout << bit(euler.l(v) + 1) << endl;
		}
	}
}

#line 1 "test/EulerTourForEdge.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_D"
#line 2 "Graph/EulerTourForEdge.cpp"
#include <vector>
#include <utility>
#include <cassert>
#include <functional>

class EulerTourForEdge {
	std::vector<std::vector<int>> graph;
	std::vector<int> ls, rs;
	int pos = 0;
	bool flag = false;
	void dfs(int v, int p = -1) {
		ls[v] = pos++;
		for (int u : graph[v])
			if (u != p) {
				dfs(u, v);
			}
		rs[v] = pos++;
	}

public:
	EulerTourForEdge(int n) : graph(n), ls(n), rs(n) {}
	EulerTourForEdge(const std::vector<std::vector<int>>& _graph)
	    : graph(_graph), ls(graph.size()), rs(graph.size()) {}
	void add_edge(int u, int v) {
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	void build(int root = 0) {
		flag = true;
		pos = 0;
		dfs(root);
	}
	int size() const {
		assert(flag);
		return pos;
	}
	int l(int i) const {
		assert(flag);
		return ls[i];
	}
	int r(int i) const {
		assert(flag);
		return rs[i];
	}
	std::pair<int, int> operator()(int i) {
		assert(flag);
		return {ls[i], rs[i]};
	}
	const std::vector<int>& get_ls() const {
		return ls;
	}
	const std::vector<int>& get_rs() const {
		return rs;
	}
	int operator[](int i) {
		assert(flag);
		return ls[i];
	}
	template <class T> auto call(int v, std::function<T(int, int)>&& f) {
		assert(flag);
		return f(ls[v], rs[v]);
	}
};
#line 4 "DataStructure/BinaryIndexedTree.cpp"

template <class T> class BinaryIndexedTree {
public:
	using value_type = T;

private:
	int n, n2;
	std::vector<value_type> a;

public:
	BinaryIndexedTree(int n_) : n(n_), n2(1), a(n_ + 1) {
		while (n2 < n) n2 *= 2;
		n2 /= 2;
	}
	value_type operator()(int i) const {  // [0, i)
		if (i == 0) return 0;
		assert(0 < i && i <= n);
		value_type result = 0;
		for (; i > 0; i -= i & -i) {
			result += a[i];
		}
		return result;
	}
	value_type operator()(int l, int r) const {  // [l, r)
		return operator()(r) - operator()(l);
	}
	value_type operator[](int i) const {
		return operator()(i, i + 1);
	}
	void add(int i, value_type x) {
		assert(0 < ++i);
		for (; i <= n; i += i & -i) {
			a[i] += x;
		}
	}
	int lower_bound(value_type k) const {
		if (k <= 0) return 0;
		int result = 0;
		for (int i = n2; i > 0; i /= 2) {
			if (result + i <= n && a[result + i] < k) {
				k -= a[result + i];
				result += i;
			}
		}
		return result;
	}
	std::vector<value_type> to_a() const {
		std::vector<value_type> result(n);
		for (int i = 0; i < n; ++i) {
			result[i] = operator[](i);
		}
		return result;
	}
};
#line 4 "test/EulerTourForEdge.test.cpp"
#include <iostream>
#line 6 "test/EulerTourForEdge.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for (vector<int>& v : g) {
		int k;
		cin >> k;
		v.resize(k);
		for (int& j : v) {
			cin >> j;
		}
	}

	EulerTourForEdge euler(g);
	euler.build();

	BinaryIndexedTree<long long> bit(euler.size());
	int q;
	cin >> q;
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int v;
			long long w;
			cin >> v >> w;
			bit.add(euler.l(v), +w);
			bit.add(euler.r(v), -w);
		} else if (com == 1) {
			int v;
			cin >> v;
			cout << bit(euler.l(v) + 1) << endl;
		}
	}
}

Back to top page