rerooting (全方位木DP)
(src/graph/rerooting.hpp)

• View this file on GitHub
• Last update: 2023-04-04 17:31:56+09:00
• Include: #include "src/graph/rerooting.hpp"

概要

与えられた木に対する動的計画法を全ての頂点についてその頂点が木全体の根だった時の結果を計算します。

具体的には、結合則を持つ二項演算 $\oplus$ について

$\displaystyle f(v) = \bigoplus_{x \in \text{child of v}} f(x)$

各 $v$ が根の時の $f(v)$ を求めます。

この説明間違ってそう

機能

コンストラクタ

(1) zawa::rerooting<vertex, edge>(const vertex& _identity, std::size_t _N)

グラフを $N$ 頂点 $0$ 辺で初期化します。

テンプレート引数vertex: 二項演算の要素を表す構造体です。 $f(v)$ を計算する時に必要なデータを取り入れてください

テンプレート引数: edge: 辺にもたせるデータの構造体です。 辺の移動によって $f(v)$ に影響を及ぼすなら、そのデータを取り入れてください

_identity: は二項演算の単位元です。必ず指定してください

_N: は木の頂点数です

メンバ

addEdge

void addEdge(int u, int v, const edge& e)

グラフの辺集合に $(u, v)$ をデータにeをもたせた状態で追加します(無向)。

制約
グラフは木である必要があります。$N - 1$ 回より多くのaddEdgeを呼び出すとassertに引っかかります。サイクルが存在するかの判定は行いません (追加予定?)

計算量
eの空間計算量に依存

changeEdge

void changeEdge(int i, const edge& e)

i番目に追加した辺のデータを eに変更します。

未テストです

制約
iにaddEdgeの呼び出し回数以上の値を指定するとassertにひっかかります

計算量
eの空間計算量に依存

getEdge

inline edgeinfo getEdge(int i) const 

i番目にaddEdgeで追加した辺の情報を得ます。

edgeinfoは以下のメンバをもつ構造体です。

edgeinfo
	: int u
	: int v それぞれ隣接する頂点
	: edge dat 格納されているデータ

制約
iにaddEdgeの呼び出し回数以上の値を指定するとassertにひっかかります

計算量
eの空間計算量に依存

get

inline vertex get(int i) const

頂点 $i$ のデータを返します。

制約

$0\ \le\ i\ <\ N$

assign

void assign(int i, const vertex& v)

頂点 $i$ のデータにvを代入します。

制約

$0\ \le\ i\ <\ N$

run

std::vector<vertex> run<F1, F2>(const F1& merge, const F2& walk)

全方位木DPを実行します。

mergeは $u\oplus v$ を行う関数です。

vertex merge(vertex a, vertex b, int x, int v)

頂点vのデータ aに頂点xのデータbをマージします。順番がカス！！

無名引数でも動作します。

walkは辺を渡った時のvertexのデータの変更を行う関数です。

vertex edge(vertex a, edge e, int x, int v)

頂点x のデータ a が辺 e を渡って頂点 vへ移動する。

無名引数でも動作します。

制約

以前にaddEdgeを丁度 $N - 1$ 回実行している。グラフは木である

計算量

mergeやwalkが $O(f)$ で動作するとして、 $O(fN)$

ドキュメントの書き方わからん！test.cppで使い方を確認してくれ未来の自分！！！

参考

• ABC222 editorial
• もうひとつの全方位木DP

Verified with

• test/ABC220-F.test.cpp
• test/ABC222-F.test.cpp
• test/AOJ1595.test.cpp
• test/rerooting.test.cpp

Code

#pragma once

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

namespace zawa {

template <class vertex, class edge>
class rerooting {
private:
	vertex identity;
	std::vector<edge> edges;
	std::vector<std::pair<int, int>> pos;
	std::vector<vertex> vertices;
	int edgeNum = 0;
	int N;

public:
	struct edgeInfo {
		int u, v;
		edge dat;
		edgeInfo(int _u, int _v, const edge& _dat) : u(_u), v(_v), dat(_dat) {}
	};

	rerooting(const vertex& _identity, std::size_t _N) 
		: identity(_identity), edges(_N - 1), pos(_N - 1), vertices(_N), N(_N) {
			assert(0 < _N);
	}	

	void addEdge(int u, int v, const edge& e) {
		assert(edgeNum < N - 1);
		assert(0 <= u and u < N);
		assert(0 <= v and v < N);
		pos[edgeNum] = { u, v };
		edges[edgeNum] = e;
		edgeNum++;
	}

	inline edgeInfo getEdge(int i) const {
		assert(i < edgeNum);
		return edgeInfo{ pos[i].first, pos[i].second, edges[i] };
	}

	inline vertex get(int i) const {
		assert(0 <= i and i < N);
		return vertices[i];
	}

	void changeEdge(int i, const edge& e) {
		assert(i < edgeNum);
		edges[i] = e;
	}

	void assign(int i, const vertex& v) {
		assert(0 <= i and i < N);
		vertices[i] = v;
	}

	template <class F1, class F2>
	std::vector<vertex> run(const F1& merge, const F2& walk) {
		assert(edgeNum == N - 1);
		std::vector<std::vector<std::pair<int, int>>> G(N);
		for (int i = 0 ; i < N - 1 ; i++) {
			const auto& [u, v] = pos[i];
			G[u].emplace_back(v, i);
			G[v].emplace_back(u, i);
		}
		auto dfs = [&](auto dfs, int v, int p) -> vertex {
			for (const auto& [x, i] : G[v]) if (x != p)
				vertices[v] = merge(vertices[v], walk(dfs(dfs, x, v), edges[i], x, v), x, v);
			return vertices[v];
		};
		dfs(dfs, 0, -1);
		std::vector<vertex> res(N, identity);
		auto reroot = [&](auto reroot, int v, int p, const vertex& propagating) -> void {
			std::vector<vertex> prefix(G[v].size() + 1, identity), suffix = prefix;
			for (int i = 0 ; i < (int)G[v].size() ; i++) {
				const auto& [x, j] = G[v][i];
				prefix[i + 1] = merge(prefix[i], walk((x == p ? propagating : vertices[x]), edges[j], x, v), x, v);
			}
			for (int i = (int)G[v].size() ; i > 0 ; i--) {
				const auto& [x, j] = G[v][i - 1];
				suffix[i - 1] = merge(suffix[i], walk((x == p ? propagating : vertices[x]), edges[j], x, v), x, v);
			}
			res[v] = prefix.back();
			for (int i = 0 ; i < (int)G[v].size() ; i++) {
				auto [x, _] = G[v][i];
				if (x != p) reroot(reroot, x, v, merge(prefix[i], suffix[i + 1], x, v));
			}
		};
		reroot(reroot, 0, -1, identity);
		return res;
	}
};

} // namespace zawa

#line 2 "src/graph/rerooting.hpp"

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

namespace zawa {

template <class vertex, class edge>
class rerooting {
private:
	vertex identity;
	std::vector<edge> edges;
	std::vector<std::pair<int, int>> pos;
	std::vector<vertex> vertices;
	int edgeNum = 0;
	int N;

public:
	struct edgeInfo {
		int u, v;
		edge dat;
		edgeInfo(int _u, int _v, const edge& _dat) : u(_u), v(_v), dat(_dat) {}
	};

	rerooting(const vertex& _identity, std::size_t _N) 
		: identity(_identity), edges(_N - 1), pos(_N - 1), vertices(_N), N(_N) {
			assert(0 < _N);
	}	

	void addEdge(int u, int v, const edge& e) {
		assert(edgeNum < N - 1);
		assert(0 <= u and u < N);
		assert(0 <= v and v < N);
		pos[edgeNum] = { u, v };
		edges[edgeNum] = e;
		edgeNum++;
	}

	inline edgeInfo getEdge(int i) const {
		assert(i < edgeNum);
		return edgeInfo{ pos[i].first, pos[i].second, edges[i] };
	}

	inline vertex get(int i) const {
		assert(0 <= i and i < N);
		return vertices[i];
	}

	void changeEdge(int i, const edge& e) {
		assert(i < edgeNum);
		edges[i] = e;
	}

	void assign(int i, const vertex& v) {
		assert(0 <= i and i < N);
		vertices[i] = v;
	}

	template <class F1, class F2>
	std::vector<vertex> run(const F1& merge, const F2& walk) {
		assert(edgeNum == N - 1);
		std::vector<std::vector<std::pair<int, int>>> G(N);
		for (int i = 0 ; i < N - 1 ; i++) {
			const auto& [u, v] = pos[i];
			G[u].emplace_back(v, i);
			G[v].emplace_back(u, i);
		}
		auto dfs = [&](auto dfs, int v, int p) -> vertex {
			for (const auto& [x, i] : G[v]) if (x != p)
				vertices[v] = merge(vertices[v], walk(dfs(dfs, x, v), edges[i], x, v), x, v);
			return vertices[v];
		};
		dfs(dfs, 0, -1);
		std::vector<vertex> res(N, identity);
		auto reroot = [&](auto reroot, int v, int p, const vertex& propagating) -> void {
			std::vector<vertex> prefix(G[v].size() + 1, identity), suffix = prefix;
			for (int i = 0 ; i < (int)G[v].size() ; i++) {
				const auto& [x, j] = G[v][i];
				prefix[i + 1] = merge(prefix[i], walk((x == p ? propagating : vertices[x]), edges[j], x, v), x, v);
			}
			for (int i = (int)G[v].size() ; i > 0 ; i--) {
				const auto& [x, j] = G[v][i - 1];
				suffix[i - 1] = merge(suffix[i], walk((x == p ? propagating : vertices[x]), edges[j], x, v), x, v);
			}
			res[v] = prefix.back();
			for (int i = 0 ; i < (int)G[v].size() ; i++) {
				auto [x, _] = G[v][i];
				if (x != p) reroot(reroot, x, v, merge(prefix[i], suffix[i + 1], x, v));
			}
		};
		reroot(reroot, 0, -1, identity);
		return res;
	}
};

} // namespace zawa

Back to top page