test/tree/euler_tour/atcoder_abc294_g.test.cpp

• View this file on GitHub
• Last update: 2023-12-14 18:25:11+09:00
• Problem: https://atcoder.jp/contests/abc294/tasks/abc294_g

Depends on

• Segment tree (src/datastructure/segment_tree.hpp)
• Euler Tour (src/tree/euler_tour.hpp)

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc294/tasks/abc294_g

#include "src/datastructure/segment_tree.hpp"
#include "src/tree/euler_tour.hpp"

#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<tuple<int, int, long long>> uvw(n - 1);
	EulerTour et(n);
	for (int i = 0; i < n - 1; ++i) {
		auto &[u, v, w] = uvw[i];
		cin >> u >> v >> w;
		--u, --v;
		et.add_edge(u, v);
	}
	et.build();
	SegmentTree st([](long long a, long long b) { return a + b; }, 0LL);
	vector<long long> weight(2UL * n);
	for (int i = 1; i < n; ++i) {
		auto [u, v, w] = uvw[i - 1];
		auto [down, up] = et.index(et.child(u, v));
		weight[down] = w;
		weight[up] = -w;
	}
	st.build(weight);

	int q;
	cin >> q;
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int i;
			long long w;
			cin >> i >> w;
			auto [u, v, _] = uvw[i - 1];
			auto update = [&](int i, long long x) { st.update(i, x); };
			et.update_edge(u, v, w, update);
		} else {
			int u, v;
			cin >> u >> v;
			long long res = 0;
			auto query = [&](int l, int r) { res += st.find(l, r); };
			et.query_edge(u - 1, v - 1, query);
			cout << res << endl;
		}
	}

	return 0;
}

#line 1 "test/tree/euler_tour/atcoder_abc294_g.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc294/tasks/abc294_g

#line 1 "src/datastructure/segment_tree.hpp"



#include <vector>

template<class T, class F>
class SegmentTree { // 0-indexed
private:
	int n_{};
	std::vector<T> tree;
	F f; // function<T(T, T)>
	T ti;

public:
	SegmentTree(F f, T ti) : f(f), ti(ti) {}

	void init(int n) {
		n_ = 1;
		while (n_ < n) n_ *= 2;
		tree.assign(2 * n_, ti);
	}

	void build(std::vector<T> const &v) {
		int const N = v.size();
		init(N);
		for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
		for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	void update(int i, T const &x) {
		i += n_;
		tree[i] = x;
		while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	T find(int l, int r) { // [l, r)
		l += n_, r += n_;
		T ll = ti, rr = ti;
		while (l < r) {
			if (l & 1) ll = f(ll, tree[l++]);
			if (r & 1) rr = f(tree[--r], rr);
			l >>= 1, r >>= 1;
		}
		return f(ll, rr);
	}

	T at(int i) { return tree[i + n_]; }
};


#line 1 "src/tree/euler_tour.hpp"



#line 5 "src/tree/euler_tour.hpp"

#include <algorithm>
#include <utility>
#line 9 "src/tree/euler_tour.hpp"

class EulerTour {
private:
	static std::pair<int, int> min(std::pair<int, int> &a, std::pair<int, int> &b) {
		return std::min(a, b);
	}

	std::vector<int> down, up, depth, terminal;
	SegmentTree<std::pair<int, int>, decltype(&min)> st;
	std::vector<std::vector<int>> G;

	void dfs(int v, int p, int d) {
		depth[terminal.size()] = d;
		down[v] = terminal.size();
		terminal.emplace_back(v);
		for (int u : G[v]) {
			if (u == p) continue;
			dfs(u, v, d + 1);
		}
		depth[terminal.size()] = d - 1;
		up[v] = terminal.size();
		terminal.emplace_back(p);
	}

public:
	EulerTour(int n) : down(n), up(n), depth(n << 1), st(min, {1 << 30, -1}), G(n) {}

	void add_edge(int u, int v) {
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}

	void build(int root = 0) {
		terminal.clear();
		dfs(root, -1, 0);
		std::vector<std::pair<int, int>> dep(terminal.size());
		for (int i = 0; i < (int)terminal.size(); ++i) dep[i] = {depth[i], terminal[i]};
		st.build(dep);
	}

	std::pair<int, int> index(int v) { return {down[v], up[v]}; };

	int parent(int u, int v) { return depth[down[u]] < depth[down[v]] ? u : v; }

	int child(int u, int v) { return depth[down[u]] < depth[down[v]] ? v : u; }

	int lca(int u, int v) {
		if (down[u] > down[v]) std::swap(u, v);
		return st.find(down[u], down[v] + 1).second;
	}

	template<class F>
	void query_vertex(int u, int v, F const &f) {
		int a = lca(u, v);
		f(down[a], down[u] + 1);
		f(down[a] + 1, down[v] + 1);
	}

	template<class F>
	void query_edge(int u, int v, F const &f) {
		int a = lca(u, v);
		f(down[a] + 1, down[u] + 1);
		f(down[a] + 1, down[v] + 1);
	}

	template<class T, class F>
	void update_vertex(int v, T x, F const &f) {
		f(down[v], x);
		f(up[v], -x);
	}

	template<class T, class F>
	void update_edge(int u, int v, T x, F const &f) {
		update_vertex(child(u, v), x, f);
	}
};


#line 5 "test/tree/euler_tour/atcoder_abc294_g.test.cpp"

#include <iostream>
#include <tuple>
#line 9 "test/tree/euler_tour/atcoder_abc294_g.test.cpp"

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<tuple<int, int, long long>> uvw(n - 1);
	EulerTour et(n);
	for (int i = 0; i < n - 1; ++i) {
		auto &[u, v, w] = uvw[i];
		cin >> u >> v >> w;
		--u, --v;
		et.add_edge(u, v);
	}
	et.build();
	SegmentTree st([](long long a, long long b) { return a + b; }, 0LL);
	vector<long long> weight(2UL * n);
	for (int i = 1; i < n; ++i) {
		auto [u, v, w] = uvw[i - 1];
		auto [down, up] = et.index(et.child(u, v));
		weight[down] = w;
		weight[up] = -w;
	}
	st.build(weight);

	int q;
	cin >> q;
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int i;
			long long w;
			cin >> i >> w;
			auto [u, v, _] = uvw[i - 1];
			auto update = [&](int i, long long x) { st.update(i, x); };
			et.update_edge(u, v, w, update);
		} else {
			int u, v;
			cin >> u >> v;
			long long res = 0;
			auto query = [&](int l, int r) { res += st.find(l, r); };
			et.query_edge(u - 1, v - 1, query);
			cout << res << endl;
		}
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.txt	AC	143 ms	8 MB
g++	00_sample_01.txt	AC	14 ms	8 MB
g++	00_sample_02.txt	AC	13 ms	7 MB
g++	00_sample_03.txt	AC	15 ms	7 MB
g++	01_handmade_03.txt	AC	846 ms	67 MB
g++	01_handmade_04.txt	AC	851 ms	67 MB
g++	01_handmade_05.txt	AC	914 ms	66 MB
g++	01_handmade_06.txt	AC	826 ms	116 MB
g++	01_handmade_07.txt	AC	776 ms	84 MB
g++	01_handmade_08.txt	AC	677 ms	61 MB
g++	01_handmade_09.txt	AC	872 ms	63 MB
g++	01_handmade_10.txt	AC	348 ms	7 MB
g++	02_random_10.txt	AC	266 ms	31 MB
g++	02_random_11.txt	AC	276 ms	31 MB
g++	02_random_12.txt	AC	385 ms	54 MB
g++	02_random_13.txt	AC	641 ms	65 MB
g++	02_random_14.txt	AC	540 ms	65 MB
g++	02_random_15.txt	AC	664 ms	57 MB
g++	02_random_16.txt	AC	365 ms	15 MB
g++	02_random_17.txt	AC	444 ms	38 MB
g++	02_random_18.txt	AC	461 ms	37 MB
g++	02_random_19.txt	AC	453 ms	63 MB
g++	02_random_20.txt	AC	624 ms	42 MB
g++	02_random_21.txt	AC	676 ms	111 MB
g++	02_random_22.txt	AC	430 ms	49 MB
g++	02_random_23.txt	AC	329 ms	20 MB
g++	02_random_24.txt	AC	267 ms	31 MB
g++	02_random_25.txt	AC	531 ms	93 MB
g++	02_random_26.txt	AC	195 ms	15 MB
g++	02_random_27.txt	AC	625 ms	56 MB
g++	02_random_28.txt	AC	224 ms	39 MB
g++	02_random_29.txt	AC	289 ms	32 MB
g++	02_random_30.txt	AC	329 ms	55 MB
g++	02_random_31.txt	AC	581 ms	40 MB
g++	02_random_32.txt	AC	364 ms	37 MB
g++	02_random_33.txt	AC	856 ms	63 MB
g++	02_random_34.txt	AC	369 ms	41 MB
g++	02_random_35.txt	AC	651 ms	56 MB
g++	02_random_36.txt	AC	621 ms	55 MB
g++	02_random_37.txt	AC	496 ms	63 MB
g++	02_random_38.txt	AC	760 ms	57 MB
g++	02_random_39.txt	AC	474 ms	65 MB
g++	02_random_40.txt	AC	659 ms	40 MB
g++	02_random_41.txt	AC	534 ms	64 MB
g++	02_random_42.txt	AC	586 ms	95 MB
g++	02_random_43.txt	AC	566 ms	85 MB
g++	02_random_44.txt	AC	521 ms	95 MB
g++	02_random_45.txt	AC	691 ms	76 MB
g++	02_random_46.txt	AC	373 ms	35 MB
g++	02_random_47.txt	AC	616 ms	59 MB
g++	02_random_48.txt	AC	610 ms	55 MB
g++	02_random_49.txt	AC	310 ms	35 MB
g++	02_random_50.txt	AC	757 ms	55 MB
g++	02_random_51.txt	AC	959 ms	66 MB
g++	02_random_52.txt	AC	777 ms	66 MB
g++	02_random_53.txt	AC	886 ms	66 MB
g++	02_random_54.txt	AC	560 ms	66 MB
g++	02_random_55.txt	AC	947 ms	66 MB
g++	02_random_56.txt	AC	830 ms	67 MB
g++	02_random_57.txt	AC	714 ms	67 MB
g++	02_random_58.txt	AC	842 ms	67 MB
g++	02_random_59.txt	AC	625 ms	67 MB
g++	02_random_60.txt	AC	979 ms	67 MB
g++	02_random_61.txt	AC	836 ms	98 MB
g++	02_random_62.txt	AC	693 ms	91 MB
g++	02_random_63.txt	AC	1019 ms	91 MB
g++	02_random_64.txt	AC	643 ms	97 MB
g++	02_random_65.txt	AC	931 ms	115 MB
g++	02_random_66.txt	AC	686 ms	61 MB
g++	02_random_67.txt	AC	722 ms	61 MB
g++	02_random_68.txt	AC	755 ms	61 MB
g++	02_random_69.txt	AC	516 ms	61 MB
g++	02_random_70.txt	AC	821 ms	61 MB
clang++	00_sample_00.txt	AC	12 ms	9 MB
clang++	00_sample_01.txt	AC	12 ms	9 MB
clang++	00_sample_02.txt	AC	11 ms	9 MB
clang++	00_sample_03.txt	AC	12 ms	13 MB
clang++	01_handmade_03.txt	AC	817 ms	71 MB
clang++	01_handmade_04.txt	AC	750 ms	71 MB
clang++	01_handmade_05.txt	AC	782 ms	70 MB
clang++	01_handmade_06.txt	AC	1120 ms	133 MB
clang++	01_handmade_07.txt	AC	779 ms	95 MB
clang++	01_handmade_08.txt	AC	729 ms	64 MB
clang++	01_handmade_09.txt	AC	797 ms	67 MB
clang++	01_handmade_10.txt	AC	394 ms	13 MB
clang++	02_random_10.txt	AC	299 ms	33 MB
clang++	02_random_11.txt	AC	283 ms	35 MB
clang++	02_random_12.txt	AC	366 ms	54 MB
clang++	02_random_13.txt	AC	643 ms	69 MB
clang++	02_random_14.txt	AC	559 ms	67 MB
clang++	02_random_15.txt	AC	841 ms	58 MB
clang++	02_random_16.txt	AC	306 ms	19 MB
clang++	02_random_17.txt	AC	530 ms	42 MB
clang++	02_random_18.txt	AC	461 ms	41 MB
clang++	02_random_19.txt	AC	466 ms	69 MB
clang++	02_random_20.txt	AC	606 ms	44 MB
clang++	02_random_21.txt	AC	728 ms	127 MB
clang++	02_random_22.txt	AC	505 ms	55 MB
clang++	02_random_23.txt	AC	361 ms	24 MB
clang++	02_random_24.txt	AC	305 ms	37 MB
clang++	02_random_25.txt	AC	454 ms	104 MB
clang++	02_random_26.txt	AC	202 ms	17 MB
clang++	02_random_27.txt	AC	579 ms	58 MB
clang++	02_random_28.txt	AC	218 ms	43 MB
clang++	02_random_29.txt	AC	309 ms	34 MB
clang++	02_random_30.txt	AC	325 ms	57 MB
clang++	02_random_31.txt	AC	563 ms	44 MB
clang++	02_random_32.txt	AC	379 ms	39 MB
clang++	02_random_33.txt	AC	840 ms	67 MB
clang++	02_random_34.txt	AC	388 ms	47 MB
clang++	02_random_35.txt	AC	641 ms	59 MB
clang++	02_random_36.txt	AC	624 ms	59 MB
clang++	02_random_37.txt	AC	619 ms	67 MB
clang++	02_random_38.txt	AC	539 ms	59 MB
clang++	02_random_39.txt	AC	480 ms	69 MB
clang++	02_random_40.txt	AC	576 ms	42 MB
clang++	02_random_41.txt	AC	671 ms	74 MB
clang++	02_random_42.txt	AC	559 ms	106 MB
clang++	02_random_43.txt	AC	570 ms	97 MB
clang++	02_random_44.txt	AC	539 ms	107 MB
clang++	02_random_45.txt	AC	688 ms	88 MB
clang++	02_random_46.txt	AC	355 ms	37 MB
clang++	02_random_47.txt	AC	565 ms	60 MB
clang++	02_random_48.txt	AC	673 ms	54 MB
clang++	02_random_49.txt	AC	326 ms	39 MB
clang++	02_random_50.txt	AC	720 ms	57 MB
clang++	02_random_51.txt	AC	975 ms	68 MB
clang++	02_random_52.txt	AC	674 ms	68 MB
clang++	02_random_53.txt	AC	838 ms	72 MB
clang++	02_random_54.txt	AC	586 ms	68 MB
clang++	02_random_55.txt	AC	880 ms	68 MB
clang++	02_random_56.txt	AC	809 ms	67 MB
clang++	02_random_57.txt	AC	728 ms	69 MB
clang++	02_random_58.txt	AC	823 ms	69 MB
clang++	02_random_59.txt	AC	593 ms	73 MB
clang++	02_random_60.txt	AC	897 ms	67 MB
clang++	02_random_61.txt	AC	972 ms	109 MB
clang++	02_random_62.txt	AC	730 ms	103 MB
clang++	02_random_63.txt	AC	943 ms	102 MB
clang++	02_random_64.txt	AC	637 ms	108 MB
clang++	02_random_65.txt	AC	884 ms	130 MB
clang++	02_random_66.txt	AC	769 ms	63 MB
clang++	02_random_67.txt	AC	636 ms	65 MB
clang++	02_random_68.txt	AC	743 ms	65 MB
clang++	02_random_69.txt	AC	528 ms	61 MB
clang++	02_random_70.txt	AC	794 ms	65 MB

Back to top page