Top Tree

tree/top_tree.hpp · GitHub で見る

共通ページ

辺の追加・削除で形が変わる森の木 DP を管理します。経路をつなぐ compress と、同じ頂点へ接続する枝をまとめる rake を定義します。逆元は不要で、部分木の最小値・直径・独立集合の数なども扱えます。

#include "lib/tree/top_tree.hpp"
#include <iostream>

struct SumDP {
	using Vertex = long long;
	using Point = long long;
	using Path = long long;
	static Point point_identity() { return 0; }
	static Point rake(Point a, Point b) { return a + b; }
	static Path compress(Path a, Path b) { return a + b; }
	static Point add_edge(Path a) { return a; }
	static Path add_vertex(Point a, Vertex v) { return a + v; }
};

int main() {
	TopTree<SumDP> tree({1, 2, 3, 4});
	tree.link(0, 1);
	tree.link(1, 2);
	tree.link(1, 3);
	std::cout << tree.all_prod(0) << '\n';        // 10
	std::cout << tree.subtree_prod(0, 1) << '\n'; // 9
	tree.set(2, 7);
	tree.cut(1, 3);
	std::cout << tree.all_prod(2) << '\n';        // 10
	std::cout << tree.all_prod(3) << '\n';        // 4
}

操作	内容・返り値	計算量
TopTree<DP>()	頂点のない森を作る	\(O(1)\)
TopTree<DP>(values)	頂点番号順の vector<Vertex> から、辺のない森を作る	\(O(n)\)
size() / empty()	頂点数の int／頂点がないかの bool	\(O(1)\)
get(v)	頂点値の const Vertex&	\(O(1)\)
set(v,value)	頂点値を const Vertex& で置き換える。返り値は void	償却 \(O(\log n)\)
same(u,v)	同じ連結成分かの bool	償却 \(O(\log n)\)
link(u,v)	無向辺を追加し、成功時に true を返す	償却 \(O(\log n)\)
cut(u,v)	無向辺を削除し、存在した場合に true を返す	償却 \(O(\log n)\)
all_prod(root)	root を根とする連結成分全体の Path	償却 \(O(\log n)\)
subtree_prod(root,v)	root を根とする v の部分木の Path	償却 \(O(\log n)\)
prod(u,v)	u から v への経路に沿って、枝も含めた連結成分全体を集約した Path	償却 \(O(\log n)\)
Vertex / Point / Path	DP に指定した型の別名	—（型）

頂点番号は 0 <= v < size() です。空の森では size()・empty() のみ使用できます。孤立点も扱えます。link は自己ループ・多重辺・閉路を作る場合に false を返します。cut は辺がない場合や自己ループの指定で false を返します。失敗しても頂点値と辺集合は変わりません。頂点の追加・削除、遅延更新は扱いません。

subtree_prod(root,v) の 2 頂点と prod(u,v) の 2 頂点は連結である必要があります。根はクエリごとに指定でき、以前の操作の根に依存しません。all_prod(root) と subtree_prod(root,v) は、それぞれ root・v の 1 頂点を境界の経路とし、そのほかを枝に畳んだ値です。孤立点では add_vertex(point_identity(), get(v)) になります。

get の参照は、そのオブジェクトの破棄・代入まで有効です。set は参照先の値を書き換えます。オブジェクトをコピーした場合は独立した森になります。DP の値はコピー・代入・交換可能な型にします。

DP の定義

型・関数	引数と返り値	計算量
DP::Vertex	頂点 1 個の情報	—（型）
DP::Point	同じ親へ接続する、互いに交わらない枝の集約。親の頂点値は含めない	—（型）
DP::Path	向きのある経路と、その経路に付く枝の集約	—（型）
DP::point_identity()	枝がない状態の Point を返す	\(O(1)\) を仮定
DP::rake(a,b)	Point 同士を併合し、Point を返す	\(O(1)\) を仮定
DP::compress(a,b)	Path の a の末尾と b の先頭を辺でつなぎ、a から b の向きの Path を返す。頂点の重複はない	\(O(1)\) を仮定
DP::add_edge(path)	Path の先頭を親へ接続する 1 本の枝として扱い、Point を返す。親は含めない	\(O(1)\) を仮定
DP::add_vertex(point,vertex)	枝を表す Point に親の Vertex を加え、その頂点だけを境界の経路とする Path を返す	\(O(1)\) を仮定

rake は可換モノイド、compress は結合則を満たす演算にします。空の経路は扱わないため、path_identity() は不要です。compress の逆方向の値はライブラリ内部で同じ頂点を逆順に集約して保持するので、reverse() も不要です。Point の枝には順序を持たせられません。

さらに、同じ木を異なる順序で compress・rake しても、同じ DP を表す必要があります。特に、子の経路を主経路に続ける場合と、枝に畳む場合を一致させます。Point p・Vertex v・Path q に対して、次の 2 つは同じ Point を表すように定義します。

DP::add_edge(DP::compress(DP::add_vertex(p, v), q))
DP::add_edge(DP::add_vertex(DP::rake(p, DP::add_edge(q)), v))

prod(u,v) は、経路外の枝も含むクラスタです。上の SumDP では経路和ではなく連結成分の総和になります。経路上の頂点だけを集約したい場合は、Point を情報を持たない型とし、rake・add_edge で枝の情報を捨て、add_vertex で頂点自身だけを使います。順序付き一次関数合成の DP がこの例です。経路積だけが必要なら Link Cut Tree も使用できます。

辺の値と直径

辺に値を持たせる場合は、各辺を u - e - v のように中間頂点 e で分割し、その頂点に辺の値を保存します。根が変わるため、片方の端点に親辺の値を保存する方法は使用できません。辺を消す場合は 2 本の辺を cut します。必要な中間頂点は最初から values に用意しておきます。

次は、非負の頂点重みのパスについて、重みの和の最大値を管理する例です。元の頂点を重み 0、中間頂点を辺の長さにすれば、辺重み付きの直径を管理できます。

#include "lib/tree/top_tree.hpp"
#include <algorithm>
#include <iostream>

struct DiameterDP {
	using Vertex = long long;
	struct Point { long long first = 0, second = 0, diameter = 0; };
	struct Path { long long length, left, right, diameter; };
	static Point point_identity() { return {}; }
	static Point rake(Point a, Point b) {
		return {std::max(a.first, b.first), std::max({a.second, b.second, std::min(a.first, b.first)}), std::max(a.diameter, b.diameter)};
	}
	static Point add_edge(const Path& a) { return {a.left, 0, a.diameter}; }
	static Path add_vertex(Point a, Vertex v) {
		return {v, v + a.first, v + a.first, std::max(a.diameter, v + a.first + a.second)};
	}
	static Path compress(const Path& a, const Path& b) {
		return {a.length + b.length, std::max(a.left, a.length + b.left), std::max(b.right, b.length + a.right), std::max({a.diameter, b.diameter, a.right + b.left})};
	}
};

int main() {
	TopTree<DiameterDP> tree({0, 0, 0, 5, 7});
	tree.link(0, 3);
	tree.link(3, 1);
	tree.link(1, 4);
	tree.link(4, 2);
	std::cout << tree.all_prod(0).diameter << '\n'; // 12
	tree.set(3, 9);
	std::cout << tree.all_prod(2).diameter << '\n'; // 16
	tree.cut(1, 4);
	std::cout << tree.all_prod(0).diameter << '\n'; // 9
}

この DP の length は境界の経路の重み和、left・right はそれぞれ先頭・末尾からの最大パス和、diameter はクラスタ内の最大パス和です。Point は枝の高さの最大 2 個と、枝の内部の最大パス和を保持します。重みは非負とし、加算で long long があふれないようにします。

Toptree 導入編 の compress・rake と、ei1333 の Lazy Top Tree を参考にしています。

頂点数を \(n\) とし、DP の演算・値のコピーを定数時間・定数空間とすると、構築は \(O(n)\) 時間、空間は \(O(n)\) です。get・size・empty は \(O(1)\)、辺の追加・削除、連結判定、頂点更新、集約は償却 \(O(\log n)\) です。

検証コード

• test/top_tree_composite.test.cpp
• test/top_tree_subtree_sum.test.cpp

コード

#ifndef TOP_TREE_HPP
#define TOP_TREE_HPP

#include <cassert>
#include <utility>
#include <vector>

template <class DP>
class TopTree {
  public:
	using Vertex = typename DP::Vertex;
	using Path = typename DP::Path;
	using Point = typename DP::Point;

  private:
	struct Node {
		Vertex value;
		Path forward, backward;
		int child[2] = {}, parent = 0, light = 0, belong = 0;
		bool reversed = false;
	};
	struct Rake {
		Point value, sum;
		int child[2] = {}, parent = 0;
	};
	std::vector<Node> nodes_;
	std::vector<Rake> rake_;
	int free_ = 0;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < size()); }
	bool path_root(int v) const {
		int p = nodes_[v].parent;
		return !p || (nodes_[p].child[0] != v && nodes_[p].child[1] != v);
	}
	void rake_pull(int v) {
		auto& x = rake_[v];
		x.sum = x.value;
		for (int c : x.child) if (c) x.sum = DP::rake(x.sum, rake_[c].sum);
	}
	void rake_rotate(int v) {
		int p = rake_[v].parent, g = rake_[p].parent, d = rake_[p].child[1] == v;
		int c = rake_[v].child[d ^ 1];
		rake_[p].child[d] = c;
		if (c) rake_[c].parent = p;
		rake_[v].child[d ^ 1] = p, rake_[p].parent = v, rake_[v].parent = g;
		if (g) rake_[g].child[rake_[g].child[1] == p] = v;
		rake_pull(p), rake_pull(v);
	}
	void rake_splay(int v) {
		while (int p = rake_[v].parent) {
			int g = rake_[p].parent;
			if (g) rake_rotate((rake_[p].child[1] == v) == (rake_[g].child[1] == p) ? p : v);
			rake_rotate(v);
		}
	}
	int rake_insert(int root, const Point& value) {
		assert(free_);
		int v = free_;
		free_ = rake_[v].parent;
		rake_[v] = {value, value, {root, 0}, 0};
		if (root) rake_[root].parent = v;
		rake_pull(v);
		return v;
	}
	int rake_erase(int v) {
		rake_splay(v);
		int l = rake_[v].child[0], r = rake_[v].child[1];
		rake_[v].parent = free_, free_ = v;
		if (!l) {
			if (r) rake_[r].parent = 0;
			return r;
		}
		rake_[l].parent = 0;
		int root = l;
		while (rake_[root].child[1]) root = rake_[root].child[1];
		rake_splay(root);
		rake_[root].child[1] = r;
		if (r) rake_[r].parent = root;
		rake_pull(root);
		return root;
	}
	Path vertex_path(int v) const {
		const auto& x = nodes_[v];
		return DP::add_vertex(x.light ? rake_[x.light].sum : DP::point_identity(), x.value);
	}
	void pull(int v) {
		auto& x = nodes_[v];
		x.forward = x.backward = vertex_path(v);
		if (int l = x.child[0]) {
			x.forward = DP::compress(nodes_[l].forward, x.forward);
			x.backward = DP::compress(x.backward, nodes_[l].backward);
		}
		if (int r = x.child[1]) {
			x.forward = DP::compress(x.forward, nodes_[r].forward);
			x.backward = DP::compress(nodes_[r].backward, x.backward);
		}
	}
	void reverse(int v) {
		auto& x = nodes_[v];
		using std::swap;
		std::swap(x.child[0], x.child[1]);
		swap(x.forward, x.backward);
		x.reversed = !x.reversed;
	}
	void push(int v) {
		auto& x = nodes_[v];
		if (!x.reversed) return;
		for (int c : x.child) if (c) reverse(c);
		x.reversed = false;
	}
	void rotate(int v) {
		int p = nodes_[v].parent, g = nodes_[p].parent, d = nodes_[p].child[1] == v;
		int c = nodes_[v].child[d ^ 1];
		if (path_root(p)) {
			nodes_[v].belong = nodes_[p].belong;
			nodes_[p].belong = 0;
		} else nodes_[g].child[nodes_[g].child[1] == p] = v;
		nodes_[p].child[d] = c;
		if (c) nodes_[c].parent = p;
		nodes_[v].child[d ^ 1] = p, nodes_[p].parent = v, nodes_[v].parent = g;
		pull(p), pull(v);
	}
	void splay(int v) {
		push(v);
		while (!path_root(v)) {
			int p = nodes_[v].parent;
			if (!path_root(p)) {
				int g = nodes_[p].parent;
				push(g), push(p), push(v);
				rotate((nodes_[p].child[1] == v) == (nodes_[g].child[1] == p) ? p : v);
			} else push(p), push(v);
			rotate(v);
		}
	}
	void expose(int v) {
		int last = 0;
		for (int x = v; x; x = nodes_[x].parent) {
			splay(x);
			int r = nodes_[x].child[1];
			if (r) {
				nodes_[x].light = rake_insert(nodes_[x].light, DP::add_edge(nodes_[r].forward));
				nodes_[r].belong = nodes_[x].light;
			}
			if (last) {
				nodes_[x].light = rake_erase(nodes_[last].belong);
				nodes_[last].belong = 0;
			}
			nodes_[x].child[1] = last;
			pull(x), last = x;
		}
		splay(v);
	}
	void evert(int v) { expose(v); reverse(v); }

  public:
	TopTree() = default;
	explicit TopTree(std::vector<Vertex> values) {
		int n = int(values.size());
		nodes_.reserve(n + 1), rake_.reserve(n + 1);
		if (n) {
			Path path = DP::add_vertex(DP::point_identity(), values.front());
			nodes_.push_back({values.front(), path, path});
		}
		for (auto& value : values) {
			Path path = DP::add_vertex(DP::point_identity(), value);
			nodes_.push_back({std::move(value), path, path});
		}
		for (int i = 0; i <= n; ++i) rake_.push_back({DP::point_identity(), DP::point_identity(), {}, i < n ? i + 1 : 0});
		free_ = n ? 1 : 0;
	}
	int size() const { return nodes_.empty() ? 0 : int(nodes_.size()) - 1; }
	bool empty() const { return size() == 0; }
	const Vertex& get(int v) const { check(v); return nodes_[v + 1].value; }
	void set(int v, const Vertex& value) {
		check(v), ++v;
		expose(v), nodes_[v].value = value, pull(v);
	}
	bool same(int u, int v) {
		check(u), check(v), ++u, ++v;
		expose(u), expose(v);
		return u == v || nodes_[u].parent;
	}
	bool link(int u, int v) {
		check(u), check(v), ++u, ++v;
		evert(u), expose(v);
		if (u == v || nodes_[u].parent) return false;
		nodes_[u].parent = v, nodes_[v].child[1] = u;
		pull(v);
		return true;
	}
	bool cut(int u, int v) {
		check(u), check(v), ++u, ++v;
		evert(u), expose(v), push(u);
		if (nodes_[v].child[0] != u || nodes_[u].child[1]) return false;
		nodes_[v].child[0] = nodes_[u].parent = 0;
		pull(v);
		return true;
	}
	Path prod(int u, int v) {
		check(u), check(v), ++u, ++v;
		evert(u), expose(v);
		assert(u == v || nodes_[u].parent);
		return nodes_[v].forward;
	}
	Path all_prod(int root) { return subtree_prod(root, root); }
	Path subtree_prod(int root, int v) {
		check(root), check(v), ++root, ++v;
		evert(root), expose(v);
		assert(root == v || nodes_[root].parent);
		return vertex_path(v);
	}
};

#endif

Back to top page