永続 Link Cut Tree

tree/persistent_link_cut_tree.hpp · GitHub で見る

共通ページ

頂点値を持つ無向森について、辺の追加・削除、頂点値の更新、順序付き経路集約を行います。各操作は新しい版を返し、以前の版からも更新・照会できます。Link Cut Tree の頂点状態を永続配列に保存する完全永続型です。

#include "lib/tree/persistent_link_cut_tree.hpp"
#include <cassert>
#include <vector>

long long add(long long a, long long b) { return a + b; }
long long zero() { return 0; }

int main() {
	PersistentLinkCutTree<long long, add, zero, true> tree(std::vector<long long>{2, 3, 5, 7});
	auto v0 = tree.initial_root();
	auto [v1, linked01] = tree.link(v0, 0, 1);
	auto [v2, linked12] = tree.link(v1, 1, 2);
	assert(linked01 && linked12);
	auto [v3, total] = tree.prod(v2, 0, 2);
	assert(total == 10);
	auto v4 = tree.set(v3, 1, 30);
	assert(tree.prod(v4, 2, 0).value == 37);
	assert(tree.prod(v2, 0, 2).value == 10);
	auto branch = tree.link(v1, 0, 3);
	assert(branch.value && tree.prod(branch.root, 1, 3).value == 12);
	assert(!tree.same(v1, 1, 3).value);
}

型は PersistentLinkCutTree<S, op, e, commutative = false> です。S はコピー・ムーブ構築と代入が可能な頂点値、op(a,b) は結合則を満たす演算、e() はその単位元を返します。S の既定構築や等値比較は要求しません。第 4 テンプレート引数は、op が可換な場合のみ true にしてください。非可換な場合は、経路の両方向の集約を保持します。

root_type は std::uint32_t の版ハンドルです。initial_root() が初期版で、ハンドルのコピーは時間・追加領域ともに \(O(1)\) です。同じオブジェクトから返された有効なハンドルだけを渡してください。値を自分で作ったり、別オブジェクトのハンドルを混ぜたりしません。オブジェクト自体はコピー・ムーブできません。

照会を含む多くの操作は result_type<T> を返します。メンバー root は操作後の版、value は T 型の答えです。auto [next, answer] = tree.prod(version,u,v); のように構造化束縛で取り出せます。版ハンドルの root と、森の根頂点を調べる root(version,v) は異なります。

照会でも splay 木を調整し、新しい永続ノードを作る場合があります。引数の版は変わりません。次の操作には返された root を引き継ぐと、調整した補助木を再利用できます。get は補助木を変更せず、値だけを返します。

変更が不要な操作では、入力と同じハンドルを返す場合があります。異なるハンドルでも、辺集合と頂点値が同じことがあります。

頂点数を \(n\) として、0 <= n < INT_MAX、頂点番号はすべて 0 <= v < n です。頂点数は構築後に変わりません。

操作	返り値・内容
`PersistentLinkCutTree(int n = 0, span<const pair<int,int>> edges = {})`	各頂点を `e()` で初期化した森を構築
`PersistentLinkCutTree(const vector<S>& values, span<const pair<int,int>> edges = {})`	`values[v]` を頂点値とする森を構築
`size()` / `empty()`	`int` の頂点数／`bool` の空判定
`initial_root()`	`root_type` の初期版。後の操作でも変わらない
`get(version,v)`	`S` 型の頂点値。新しいノードを作らない
`set(version,v,value)`	頂点値を `value` に変更した `root_type`
`build_forest(version,edges)`	頂点値を保持し、辺を `edges` で置き換えた `root_type`
`link(version,u,v)`	`result_type<bool>`。別成分の頂点間に辺を追加し、成功なら `true`
`cut(version,u,v)`	`result_type<bool>`。辺 `u-v` を削除し、成功なら `true`
`same(version,u,v)`	`result_type<bool>`。同じ連結成分か
`prod(version,u,v)`	`result_type<S>`。`u` から `v` の順序で、両端を含む頂点値を集約
`path_size(version,u,v)` / `distance(version,u,v)`	`result_type<int>`。経路の頂点数／辺数
`jump(version,u,v,k)`	`result_type<int>`。`u` を 0 番目とする経路上の `k` 番目の頂点。範囲外は `-1`
`make_root(version,v)`	`v` をその成分の根にした `root_type`
`root(version,v)`	`result_type<int>`。`v` の成分の現在の根頂点
`lca(version,r,u,v)`	`result_type<int>`。`r` を根にしたときの `u,v` の LCA
`reserve(count)`	`void`。全版を合わせた永続配列ノード数を予約
`node_count()` / `memory_usage()`	`std::size_t`。番兵を除く作成済み永続配列ノード数／永続領域と操作用配列の予約領域のバイト数

構築時と build_forest の edges は、vector<pair<int,int>> などで渡します。自己ループ・多重辺・閉路のない森であることが必要です。各成分の根の選び方は未規定です。根を指定するときは、構築後に make_root を使います。edges が空なら全頂点が孤立します。空の森も構築でき、size() は 0、empty() は true です。空の森では頂点を指定する操作はできません。

link は u == v または既に連結な場合に false、cut は u == v または指定した辺がない場合に false を返します。失敗しても返された版の補助木は調整される場合があります。辺集合と頂点値は変わりません。

prod・path_size・distance・jump の両端は連結であることが前提です。jump は連結な経路に対し、k < 0 または k >= path_size なら -1 です。lca の 3 頂点も同じ成分に属する必要があります。u == v の経路集約はその頂点値、頂点数は 1、距離は 0 です。

経路操作は、返す版で u を根にします。lca は r を根にします。link・cut は、異なる頂点を指定した場合はまず u を根にするため、失敗した場合も根が変わり得ます。成功した link の成分の根は、結合前の v の成分の根です。cut 成功後の 2 成分の根は、それぞれ u と v です。same・root・get・set は森の根を変えません。いずれも入力版の根・辺・値は保持されます。

ノード領域は版ごとに解放しません。不要な版ハンドルを破棄しても、作成済み永続ノードはオブジェクトの破棄まで保持します。reserve(count) は count < UINT32_MAX とし、再確保後も既存ハンドルは有効です。memory_usage() は S 自体が動的確保した領域を含みません。値のコピーやモノイド演算に費用がかかる場合は、以下の計算量にもその費用が加わります。

頂点数を \(n\)、構築する辺数を \(m\) とします。初期構築は \(O(n+m)\) 時間・空間、build_forest は \(O(n\log n+m)\) 時間・\(O(n\log n)\) 追加領域です。size・empty・initial_root・node_count・memory_usage は \(O(1)\)、get は \(O(\log n)\) 時間・\(O(1)\) 追加領域です。reserve は再確保する場合、作成済み永続配列ノード数に線形の時間がかかります。

その他の操作で訪問する頂点数を \(k\)、通常の Link Cut Tree における処理量を \(r\) とすると、操作内のキャッシュと永続配列の更新により時間は \(O(r+k\log n)\)、新しい永続領域は \(O(k\log n)\) です。各操作の最悪計算量は時間・追加領域ともに \(O(n\log n)\) です。別に、再利用する操作用領域を \(O(n)\) 保持します。

build_forest と reserve を含まず、各操作が直前に返された版を引き継ぐ直線的な列では、splay の償却解析が使え、1 操作あたり償却 \(O(\log^2 n)\) です。一括構築した森の初期ポテンシャルも含めると、\(q\) 回の操作の時間・永続領域の上界は \(O((n+q)\log^2 n)\) です。任意の過去版から分岐する操作列全体には、この償却保証は適用できません。同じ古い版を毎回照会し、返された版を捨てる場合も同様です。長さ 0・1 の森で有効な頂点操作は定数時間です。

依存ライブラリ

永続配列

コード

#line 1 "tree/persistent_link_cut_tree.hpp"

#line 1 "data_structure/persistent_array.hpp"

#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

template <class T, int Log = 3>
class PersistentArray {
	static_assert(1 <= Log && Log <= 5);
  public:
	using value_type = T;
	using root_type = std::uint32_t;
  private:
	struct Node { T value; std::array<root_type, 1 << Log> child{}; };
	int n_;
	root_type initial_ = 0;
	std::vector<Node> nodes;
	root_type make(Node node) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(std::move(node));
		return result;
	}
	root_type clone(root_type root) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(nodes[root]);
		return result;
	}
	root_type update(root_type root, unsigned p, T value) {
		if (!p) return make({std::move(value), nodes[root].child});
		auto result = clone(root), current = result;
		while (p) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log;
			auto old = nodes[current].child[d];
			auto next = p ? clone(old) : make({std::move(value), nodes[old].child});
			nodes[current].child[d] = next;
			current = next;
		}
		return result;
	}
	root_type update_pair(root_type root, unsigned p, T a, unsigned q, T b) {
		if (p == q) return update(root, q, std::move(b));
		auto result = clone(root), current = result;
		while (p && q && (p & ((1 << Log) - 1)) == (q & ((1 << Log) - 1))) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log, q >>= Log;
			auto next = clone(nodes[current].child[d]);
			nodes[current].child[d] = next;
			current = next;
		}
		if (!p) nodes[current].value = std::move(a);
		else {
			unsigned d = p & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], p >> Log, std::move(a));
			nodes[current].child[d] = next;
		}
		if (!q) nodes[current].value = std::move(b);
		else {
			unsigned d = q & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], q >> Log, std::move(b));
			nodes[current].child[d] = next;
		}
		return result;
	}
	root_type build(const std::vector<T> &a, std::size_t p, std::size_t step) {
		Node node{a[p], {}};
		for (int d = 0; d < (1 << Log); ++d) {
			std::size_t next = p + step * d;
			if (next < a.size() && (d || step <= (a.size() - 1 - p) / (1 << Log)))
				node.child[d] = build(a, next, step * (1 << Log));
		}
		return make(std::move(node));
	}
	void check([[maybe_unused]] root_type root) const { assert(root < nodes.size()); }
  public:
	explicit PersistentArray(int n = 0, T value = T{}) : n_(n), nodes{Node{std::move(value), {}}} { assert(n >= 0); }
	explicit PersistentArray(const std::vector<T> &a, T default_value = T{}) : PersistentArray(0, std::move(default_value)) {
		assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
		n_ = static_cast<int>(a.size());
		if (n_) {
			std::size_t count = a.size();
			for (auto rest = (a.size() - 1) >> Log; rest; rest >>= Log) count += rest;
			reserve(count);
			initial_ = build(a, 0, 1);
		}
	}
	int size() const { return n_; }
	bool empty() const { return !n_; }
	root_type initial_root() const { return initial_; }
	T get(root_type root, int p) const {
		check(root); assert(0 <= p && p < n_);
		while (root && p) { root = nodes[root].child[p & ((1 << Log) - 1)]; p >>= Log; }
		return nodes[root].value;
	}
	root_type set(root_type root, int p, T value) {
		check(root); assert(0 <= p && p < n_);
		return update(root, static_cast<unsigned>(p), std::move(value));
	}
	root_type set_pair(root_type root, int p, T a, int q, T b) {
		check(root); assert(0 <= p && p < n_ && 0 <= q && q < n_);
		return update_pair(root, static_cast<unsigned>(p), std::move(a), static_cast<unsigned>(q), std::move(b));
	}
	void reserve(std::size_t count) { assert(count < std::numeric_limits<root_type>::max()); nodes.reserve(count + 1); }
	std::size_t node_count() const { return nodes.size() - 1; }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
};

#line 5 "tree/persistent_link_cut_tree.hpp"
#include <algorithm>
#line 9 "tree/persistent_link_cut_tree.hpp"
#include <optional>
#include <span>
#include <type_traits>
#line 14 "tree/persistent_link_cut_tree.hpp"

template<class S, auto op, auto e, bool commutative = false>
class PersistentLinkCutTree {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int child[2] = {}, parent = 0, count = 1;
		bool reversed = false;
		S value, aggregate;
		[[no_unique_address]] Back backward;
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		explicit Node(const S &value) : value(value), aggregate(value), backward(make_back(value)) {}
	};
	using Storage = PersistentArray<Node>;
	struct Slot {
		std::optional<Node> node;
		bool dirty = false;
	};
	Storage storage;
	std::vector<Slot> cache;
	std::vector<int> touched, ancestors;

static std::vector<S> initial_values(int n) {
		assert(0 <= n && n < std::numeric_limits<int>::max());
		return std::vector<S>(n, e());
	}
	static std::vector<int> forest_parents(int n, std::span<const std::pair<int, int>> edges) {
		assert(edges.size() < std::size_t(n) || (n == 0 && edges.empty()));
		std::vector<int> degree(n), neighbors(n), parent(n, -1), order;
		order.reserve(n);
		for (auto [u, v] : edges) {
			assert(0 <= u && u < n && 0 <= v && v < n && u != v);
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		for (int v = 0; v < n; ++v) if (degree[v] <= 1) order.push_back(v);
		for (std::size_t i = 0; i < order.size(); ++i) {
			int v = order[i];
			if (!degree[v]) continue;
			int p = neighbors[v];
			parent[v] = p;
			degree[v] = 0;
			neighbors[p] ^= v;
			if (--degree[p] == 1) order.push_back(p);
		}
		assert(order.size() == std::size_t(n));
		return parent;
	}
	static std::vector<Node> initial_nodes(const std::vector<S> &values, std::span<const std::pair<int, int>> edges) {
		assert(values.size() < std::size_t(std::numeric_limits<int>::max()));
		auto parent = forest_parents(static_cast<int>(values.size()), edges);
		std::vector<Node> nodes;
		nodes.reserve(values.size() + 1);
		nodes.emplace_back(e());
		nodes[0].count = 0;
		for (std::size_t v = 0; v < values.size(); ++v) {
			nodes.emplace_back(values[v]);
			nodes.back().parent = parent[v] + 1;
		}
		return nodes;
	}
	int node(int v) const {
		assert(0 <= v && v < size());
		return v + 1;
	}

public:
	using root_type = typename Storage::root_type;
	template<class T> struct result_type {
		root_type root;
		T value;
	};

private:
	class Editor {
		PersistentLinkCutTree &owner;
		root_type version;
		Node &load(int x) {
			auto &slot = owner.cache[x];
			if (!slot.node) {
				owner.touched.push_back(x);
				slot.node.emplace(owner.storage.get(version, x));
			}
			return *slot.node;
		}
		bool is_root(int x) {
			int p = read(x).parent;
			return !p || (read(p).child[0] != x && read(p).child[1] != x);
		}
		void flip(int x) {
			if (!x) return;
			auto &v = write(x);
			std::swap(v.child[0], v.child[1]);
			if constexpr (!commutative) std::swap(v.aggregate, v.backward);
			v.reversed = !v.reversed;
		}
		void push(int x) {
			if (!read(x).reversed) return;
			flip(read(x).child[0]);
			flip(read(x).child[1]);
			write(x).reversed = false;
		}
		void rotate(int x) {
			int p = read(x).parent, g = read(p).parent;
			int d = read(p).child[1] == x, c = read(x).child[d ^ 1];
			if (!is_root(p)) write(g).child[read(g).child[1] == p] = x;
			write(x).parent = g;
			write(p).child[d] = c;
			if (c) write(c).parent = p;
			write(x).child[d ^ 1] = p;
			write(p).parent = x;
			pull(p);
			pull(x);
		}

public:
		Editor(PersistentLinkCutTree &owner, root_type version) : owner(owner), version(version) {
			assert(version <= owner.storage.node_count() && owner.touched.empty());
		}
		~Editor() {
			for (int x : owner.touched) {
				owner.cache[x].node.reset();
				owner.cache[x].dirty = false;
			}
			owner.touched.clear();
			owner.ancestors.clear();
		}
		const Node &read(int x) { return load(x); }
		Node &write(int x) {
			Node &value = load(x);
			owner.cache[x].dirty = true;
			return value;
		}
		root_type commit() {
			for (int x : owner.touched) if (owner.cache[x].dirty)
				version = owner.storage.set(version, x, std::move(*owner.cache[x].node));
			return version;
		}
		template<class T> result_type<T> finish(T value) { return {commit(), std::move(value)}; }
		void pull(int x) {
			auto &v = write(x);
			const auto &l = read(v.child[0]), &r = read(v.child[1]);
			v.count = l.count + r.count + 1;
			v.aggregate = op(op(l.aggregate, v.value), r.aggregate);
			if constexpr (!commutative) v.backward = op(op(r.backward, v.value), l.backward);
		}
		void splay(int x) {
			auto &path = owner.ancestors;
			path.clear();
			for (int y = x;; y = read(y).parent) {
				path.push_back(y);
				if (is_root(y)) break;
			}
			for (auto it = path.rbegin(); it != path.rend(); ++it) push(*it);
			while (!is_root(x)) {
				int p = read(x).parent, g = read(p).parent;
				if (!is_root(p)) rotate((read(p).child[0] == x) == (read(g).child[0] == p) ? p : x);
				rotate(x);
			}
		}
		int access(int x) {
			int last = 0;
			for (int y = x; y; y = read(y).parent) {
				splay(y);
				write(y).child[1] = last;
				if (last) write(last).parent = y;
				pull(y);
				last = y;
			}
			splay(x);
			return last;
		}
		void make_root(int x) { access(x); flip(x); }
		int root(int x) {
			access(x);
			push(x);
			while (read(x).child[0]) push(x = read(x).child[0]);
			splay(x);
			return x;
		}
		int expose(int u, int v) {
			make_root(u);
			access(v);
			assert(u == v || read(u).parent != 0);
			return v;
		}
		int select(int x, int k) {
			if (k < 0 || k >= read(x).count) return -1;
			for (;;) {
				push(x);
				int l = read(x).child[0], count = read(l).count;
				if (k == count) break;
				if (k < count) x = l;
				else k -= count + 1, x = read(x).child[1];
			}
			splay(x);
			return x - 1;
		}
	};

public:
	explicit PersistentLinkCutTree(int n = 0, std::span<const std::pair<int, int>> edges = {})
		: PersistentLinkCutTree(initial_values(n), edges) {}
	explicit PersistentLinkCutTree(const std::vector<S> &values, std::span<const std::pair<int, int>> edges = {})
		: storage(initial_nodes(values, edges), Node(e())), cache(values.size() + 1) {}
	PersistentLinkCutTree(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree &operator=(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree(PersistentLinkCutTree &&) = delete;
	PersistentLinkCutTree &operator=(PersistentLinkCutTree &&) = delete;
	int size() const { return storage.size() - 1; }
	bool empty() const { return size() == 0; }
	root_type initial_root() const { return storage.initial_root(); }
	S get(root_type version, int v) const { return storage.get(version, node(v)).value; }
	root_type set(root_type version, int v, S value) {
		Editor edit(*this, version);
		int x = node(v);
		edit.access(x);
		edit.write(x).value = std::move(value);
		edit.pull(x);
		return edit.commit();
	}
	root_type make_root(root_type version, int v) {
		Editor edit(*this, version);
		edit.make_root(node(v));
		return edit.commit();
	}
	root_type build_forest(root_type version, std::span<const std::pair<int, int>> edges) {
		auto parent = forest_parents(size(), edges);
		Editor edit(*this, version);
		for (int v = 0; v < size(); ++v) {
			int x = v + 1;
			Node replacement(edit.read(x).value);
			replacement.parent = parent[v] + 1;
			edit.write(x) = std::move(replacement);
		}
		return edit.commit();
	}
	result_type<int> root(root_type version, int v) {
		Editor edit(*this, version);
		return edit.finish(edit.root(node(v)) - 1);
	}
	result_type<bool> same(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(true);
		edit.access(u);
		edit.access(v);
		return edit.finish(edit.read(u).parent != 0);
	}
	result_type<bool> link(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(u).parent) return edit.finish(false);
		edit.write(u).parent = v;
		return edit.finish(true);
	}
	result_type<bool> cut(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(v).child[0] != u || edit.read(u).child[1]) return edit.finish(false);
		edit.write(v).child[0] = 0;
		edit.write(u).parent = 0;
		edit.pull(v);
		return edit.finish(true);
	}
	result_type<S> prod(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).aggregate);
	}
	result_type<int> path_size(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).count);
	}
	result_type<int> distance(root_type version, int u, int v) {
		auto result = path_size(version, u, v);
		--result.value;
		return result;
	}
	result_type<int> jump(root_type version, int u, int v, int k) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.select(x, k));
	}
	result_type<int> lca(root_type version, int r, int u, int v) {
		Editor edit(*this, version);
		r = node(r), u = node(u), v = node(v);
		edit.make_root(r);
		edit.access(u);
		assert(r == u || edit.read(r).parent != 0);
		int w = edit.access(v);
		assert(u == v || edit.read(u).parent != 0);
		return edit.finish(w - 1);
	}
	void reserve(std::size_t count) { storage.reserve(count); }
	std::size_t node_count() const { return storage.node_count(); }
	std::size_t memory_usage() const {
		return storage.memory_usage() + cache.capacity() * sizeof(Slot)
			+ (touched.capacity() + ancestors.capacity()) * sizeof(int);
	}
};

#ifndef PERSISTENT_LINK_CUT_TREE_HPP
#define PERSISTENT_LINK_CUT_TREE_HPP

#include "../data_structure/persistent_array.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <optional>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

template<class S, auto op, auto e, bool commutative = false>
class PersistentLinkCutTree {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int child[2] = {}, parent = 0, count = 1;
		bool reversed = false;
		S value, aggregate;
		[[no_unique_address]] Back backward;
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		explicit Node(const S &value) : value(value), aggregate(value), backward(make_back(value)) {}
	};
	using Storage = PersistentArray<Node>;
	struct Slot {
		std::optional<Node> node;
		bool dirty = false;
	};
	Storage storage;
	std::vector<Slot> cache;
	std::vector<int> touched, ancestors;

	static std::vector<S> initial_values(int n) {
		assert(0 <= n && n < std::numeric_limits<int>::max());
		return std::vector<S>(n, e());
	}
	static std::vector<int> forest_parents(int n, std::span<const std::pair<int, int>> edges) {
		assert(edges.size() < std::size_t(n) || (n == 0 && edges.empty()));
		std::vector<int> degree(n), neighbors(n), parent(n, -1), order;
		order.reserve(n);
		for (auto [u, v] : edges) {
			assert(0 <= u && u < n && 0 <= v && v < n && u != v);
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		for (int v = 0; v < n; ++v) if (degree[v] <= 1) order.push_back(v);
		for (std::size_t i = 0; i < order.size(); ++i) {
			int v = order[i];
			if (!degree[v]) continue;
			int p = neighbors[v];
			parent[v] = p;
			degree[v] = 0;
			neighbors[p] ^= v;
			if (--degree[p] == 1) order.push_back(p);
		}
		assert(order.size() == std::size_t(n));
		return parent;
	}
	static std::vector<Node> initial_nodes(const std::vector<S> &values, std::span<const std::pair<int, int>> edges) {
		assert(values.size() < std::size_t(std::numeric_limits<int>::max()));
		auto parent = forest_parents(static_cast<int>(values.size()), edges);
		std::vector<Node> nodes;
		nodes.reserve(values.size() + 1);
		nodes.emplace_back(e());
		nodes[0].count = 0;
		for (std::size_t v = 0; v < values.size(); ++v) {
			nodes.emplace_back(values[v]);
			nodes.back().parent = parent[v] + 1;
		}
		return nodes;
	}
	int node(int v) const {
		assert(0 <= v && v < size());
		return v + 1;
	}

  public:
	using root_type = typename Storage::root_type;
	template<class T> struct result_type {
		root_type root;
		T value;
	};

  private:
	class Editor {
		PersistentLinkCutTree &owner;
		root_type version;
		Node &load(int x) {
			auto &slot = owner.cache[x];
			if (!slot.node) {
				owner.touched.push_back(x);
				slot.node.emplace(owner.storage.get(version, x));
			}
			return *slot.node;
		}
		bool is_root(int x) {
			int p = read(x).parent;
			return !p || (read(p).child[0] != x && read(p).child[1] != x);
		}
		void flip(int x) {
			if (!x) return;
			auto &v = write(x);
			std::swap(v.child[0], v.child[1]);
			if constexpr (!commutative) std::swap(v.aggregate, v.backward);
			v.reversed = !v.reversed;
		}
		void push(int x) {
			if (!read(x).reversed) return;
			flip(read(x).child[0]);
			flip(read(x).child[1]);
			write(x).reversed = false;
		}
		void rotate(int x) {
			int p = read(x).parent, g = read(p).parent;
			int d = read(p).child[1] == x, c = read(x).child[d ^ 1];
			if (!is_root(p)) write(g).child[read(g).child[1] == p] = x;
			write(x).parent = g;
			write(p).child[d] = c;
			if (c) write(c).parent = p;
			write(x).child[d ^ 1] = p;
			write(p).parent = x;
			pull(p);
			pull(x);
		}

	  public:
		Editor(PersistentLinkCutTree &owner, root_type version) : owner(owner), version(version) {
			assert(version <= owner.storage.node_count() && owner.touched.empty());
		}
		~Editor() {
			for (int x : owner.touched) {
				owner.cache[x].node.reset();
				owner.cache[x].dirty = false;
			}
			owner.touched.clear();
			owner.ancestors.clear();
		}
		const Node &read(int x) { return load(x); }
		Node &write(int x) {
			Node &value = load(x);
			owner.cache[x].dirty = true;
			return value;
		}
		root_type commit() {
			for (int x : owner.touched) if (owner.cache[x].dirty)
				version = owner.storage.set(version, x, std::move(*owner.cache[x].node));
			return version;
		}
		template<class T> result_type<T> finish(T value) { return {commit(), std::move(value)}; }
		void pull(int x) {
			auto &v = write(x);
			const auto &l = read(v.child[0]), &r = read(v.child[1]);
			v.count = l.count + r.count + 1;
			v.aggregate = op(op(l.aggregate, v.value), r.aggregate);
			if constexpr (!commutative) v.backward = op(op(r.backward, v.value), l.backward);
		}
		void splay(int x) {
			auto &path = owner.ancestors;
			path.clear();
			for (int y = x;; y = read(y).parent) {
				path.push_back(y);
				if (is_root(y)) break;
			}
			for (auto it = path.rbegin(); it != path.rend(); ++it) push(*it);
			while (!is_root(x)) {
				int p = read(x).parent, g = read(p).parent;
				if (!is_root(p)) rotate((read(p).child[0] == x) == (read(g).child[0] == p) ? p : x);
				rotate(x);
			}
		}
		int access(int x) {
			int last = 0;
			for (int y = x; y; y = read(y).parent) {
				splay(y);
				write(y).child[1] = last;
				if (last) write(last).parent = y;
				pull(y);
				last = y;
			}
			splay(x);
			return last;
		}
		void make_root(int x) { access(x); flip(x); }
		int root(int x) {
			access(x);
			push(x);
			while (read(x).child[0]) push(x = read(x).child[0]);
			splay(x);
			return x;
		}
		int expose(int u, int v) {
			make_root(u);
			access(v);
			assert(u == v || read(u).parent != 0);
			return v;
		}
		int select(int x, int k) {
			if (k < 0 || k >= read(x).count) return -1;
			for (;;) {
				push(x);
				int l = read(x).child[0], count = read(l).count;
				if (k == count) break;
				if (k < count) x = l;
				else k -= count + 1, x = read(x).child[1];
			}
			splay(x);
			return x - 1;
		}
	};

  public:
	explicit PersistentLinkCutTree(int n = 0, std::span<const std::pair<int, int>> edges = {})
		: PersistentLinkCutTree(initial_values(n), edges) {}
	explicit PersistentLinkCutTree(const std::vector<S> &values, std::span<const std::pair<int, int>> edges = {})
		: storage(initial_nodes(values, edges), Node(e())), cache(values.size() + 1) {}
	PersistentLinkCutTree(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree &operator=(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree(PersistentLinkCutTree &&) = delete;
	PersistentLinkCutTree &operator=(PersistentLinkCutTree &&) = delete;
	int size() const { return storage.size() - 1; }
	bool empty() const { return size() == 0; }
	root_type initial_root() const { return storage.initial_root(); }
	S get(root_type version, int v) const { return storage.get(version, node(v)).value; }
	root_type set(root_type version, int v, S value) {
		Editor edit(*this, version);
		int x = node(v);
		edit.access(x);
		edit.write(x).value = std::move(value);
		edit.pull(x);
		return edit.commit();
	}
	root_type make_root(root_type version, int v) {
		Editor edit(*this, version);
		edit.make_root(node(v));
		return edit.commit();
	}
	root_type build_forest(root_type version, std::span<const std::pair<int, int>> edges) {
		auto parent = forest_parents(size(), edges);
		Editor edit(*this, version);
		for (int v = 0; v < size(); ++v) {
			int x = v + 1;
			Node replacement(edit.read(x).value);
			replacement.parent = parent[v] + 1;
			edit.write(x) = std::move(replacement);
		}
		return edit.commit();
	}
	result_type<int> root(root_type version, int v) {
		Editor edit(*this, version);
		return edit.finish(edit.root(node(v)) - 1);
	}
	result_type<bool> same(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(true);
		edit.access(u);
		edit.access(v);
		return edit.finish(edit.read(u).parent != 0);
	}
	result_type<bool> link(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(u).parent) return edit.finish(false);
		edit.write(u).parent = v;
		return edit.finish(true);
	}
	result_type<bool> cut(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(v).child[0] != u || edit.read(u).child[1]) return edit.finish(false);
		edit.write(v).child[0] = 0;
		edit.write(u).parent = 0;
		edit.pull(v);
		return edit.finish(true);
	}
	result_type<S> prod(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).aggregate);
	}
	result_type<int> path_size(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).count);
	}
	result_type<int> distance(root_type version, int u, int v) {
		auto result = path_size(version, u, v);
		--result.value;
		return result;
	}
	result_type<int> jump(root_type version, int u, int v, int k) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.select(x, k));
	}
	result_type<int> lca(root_type version, int r, int u, int v) {
		Editor edit(*this, version);
		r = node(r), u = node(u), v = node(v);
		edit.make_root(r);
		edit.access(u);
		assert(r == u || edit.read(r).parent != 0);
		int w = edit.access(v);
		assert(u == v || edit.read(u).parent != 0);
		return edit.finish(w - 1);
	}
	void reserve(std::size_t count) { storage.reserve(count); }
	std::size_t node_count() const { return storage.node_count(); }
	std::size_t memory_usage() const {
		return storage.memory_usage() + cache.capacity() * sizeof(Slot)
			+ (touched.capacity() + ancestors.capacity()) * sizeof(int);
	}
};

#endif

#line 1 "tree/persistent_link_cut_tree.hpp"



#line 1 "data_structure/persistent_array.hpp"



#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

template <class T, int Log = 3>
class PersistentArray {
	static_assert(1 <= Log && Log <= 5);
  public:
	using value_type = T;
	using root_type = std::uint32_t;
  private:
	struct Node { T value; std::array<root_type, 1 << Log> child{}; };
	int n_;
	root_type initial_ = 0;
	std::vector<Node> nodes;
	root_type make(Node node) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(std::move(node));
		return result;
	}
	root_type clone(root_type root) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(nodes[root]);
		return result;
	}
	root_type update(root_type root, unsigned p, T value) {
		if (!p) return make({std::move(value), nodes[root].child});
		auto result = clone(root), current = result;
		while (p) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log;
			auto old = nodes[current].child[d];
			auto next = p ? clone(old) : make({std::move(value), nodes[old].child});
			nodes[current].child[d] = next;
			current = next;
		}
		return result;
	}
	root_type update_pair(root_type root, unsigned p, T a, unsigned q, T b) {
		if (p == q) return update(root, q, std::move(b));
		auto result = clone(root), current = result;
		while (p && q && (p & ((1 << Log) - 1)) == (q & ((1 << Log) - 1))) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log, q >>= Log;
			auto next = clone(nodes[current].child[d]);
			nodes[current].child[d] = next;
			current = next;
		}
		if (!p) nodes[current].value = std::move(a);
		else {
			unsigned d = p & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], p >> Log, std::move(a));
			nodes[current].child[d] = next;
		}
		if (!q) nodes[current].value = std::move(b);
		else {
			unsigned d = q & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], q >> Log, std::move(b));
			nodes[current].child[d] = next;
		}
		return result;
	}
	root_type build(const std::vector<T> &a, std::size_t p, std::size_t step) {
		Node node{a[p], {}};
		for (int d = 0; d < (1 << Log); ++d) {
			std::size_t next = p + step * d;
			if (next < a.size() && (d || step <= (a.size() - 1 - p) / (1 << Log)))
				node.child[d] = build(a, next, step * (1 << Log));
		}
		return make(std::move(node));
	}
	void check([[maybe_unused]] root_type root) const { assert(root < nodes.size()); }
  public:
	explicit PersistentArray(int n = 0, T value = T{}) : n_(n), nodes{Node{std::move(value), {}}} { assert(n >= 0); }
	explicit PersistentArray(const std::vector<T> &a, T default_value = T{}) : PersistentArray(0, std::move(default_value)) {
		assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
		n_ = static_cast<int>(a.size());
		if (n_) {
			std::size_t count = a.size();
			for (auto rest = (a.size() - 1) >> Log; rest; rest >>= Log) count += rest;
			reserve(count);
			initial_ = build(a, 0, 1);
		}
	}
	int size() const { return n_; }
	bool empty() const { return !n_; }
	root_type initial_root() const { return initial_; }
	T get(root_type root, int p) const {
		check(root); assert(0 <= p && p < n_);
		while (root && p) { root = nodes[root].child[p & ((1 << Log) - 1)]; p >>= Log; }
		return nodes[root].value;
	}
	root_type set(root_type root, int p, T value) {
		check(root); assert(0 <= p && p < n_);
		return update(root, static_cast<unsigned>(p), std::move(value));
	}
	root_type set_pair(root_type root, int p, T a, int q, T b) {
		check(root); assert(0 <= p && p < n_ && 0 <= q && q < n_);
		return update_pair(root, static_cast<unsigned>(p), std::move(a), static_cast<unsigned>(q), std::move(b));
	}
	void reserve(std::size_t count) { assert(count < std::numeric_limits<root_type>::max()); nodes.reserve(count + 1); }
	std::size_t node_count() const { return nodes.size() - 1; }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
};


#line 5 "tree/persistent_link_cut_tree.hpp"
#include <algorithm>
#line 9 "tree/persistent_link_cut_tree.hpp"
#include <optional>
#include <span>
#include <type_traits>
#line 14 "tree/persistent_link_cut_tree.hpp"

template<class S, auto op, auto e, bool commutative = false>
class PersistentLinkCutTree {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int child[2] = {}, parent = 0, count = 1;
		bool reversed = false;
		S value, aggregate;
		[[no_unique_address]] Back backward;
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		explicit Node(const S &value) : value(value), aggregate(value), backward(make_back(value)) {}
	};
	using Storage = PersistentArray<Node>;
	struct Slot {
		std::optional<Node> node;
		bool dirty = false;
	};
	Storage storage;
	std::vector<Slot> cache;
	std::vector<int> touched, ancestors;

	static std::vector<S> initial_values(int n) {
		assert(0 <= n && n < std::numeric_limits<int>::max());
		return std::vector<S>(n, e());
	}
	static std::vector<int> forest_parents(int n, std::span<const std::pair<int, int>> edges) {
		assert(edges.size() < std::size_t(n) || (n == 0 && edges.empty()));
		std::vector<int> degree(n), neighbors(n), parent(n, -1), order;
		order.reserve(n);
		for (auto [u, v] : edges) {
			assert(0 <= u && u < n && 0 <= v && v < n && u != v);
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		for (int v = 0; v < n; ++v) if (degree[v] <= 1) order.push_back(v);
		for (std::size_t i = 0; i < order.size(); ++i) {
			int v = order[i];
			if (!degree[v]) continue;
			int p = neighbors[v];
			parent[v] = p;
			degree[v] = 0;
			neighbors[p] ^= v;
			if (--degree[p] == 1) order.push_back(p);
		}
		assert(order.size() == std::size_t(n));
		return parent;
	}
	static std::vector<Node> initial_nodes(const std::vector<S> &values, std::span<const std::pair<int, int>> edges) {
		assert(values.size() < std::size_t(std::numeric_limits<int>::max()));
		auto parent = forest_parents(static_cast<int>(values.size()), edges);
		std::vector<Node> nodes;
		nodes.reserve(values.size() + 1);
		nodes.emplace_back(e());
		nodes[0].count = 0;
		for (std::size_t v = 0; v < values.size(); ++v) {
			nodes.emplace_back(values[v]);
			nodes.back().parent = parent[v] + 1;
		}
		return nodes;
	}
	int node(int v) const {
		assert(0 <= v && v < size());
		return v + 1;
	}

  public:
	using root_type = typename Storage::root_type;
	template<class T> struct result_type {
		root_type root;
		T value;
	};

  private:
	class Editor {
		PersistentLinkCutTree &owner;
		root_type version;
		Node &load(int x) {
			auto &slot = owner.cache[x];
			if (!slot.node) {
				owner.touched.push_back(x);
				slot.node.emplace(owner.storage.get(version, x));
			}
			return *slot.node;
		}
		bool is_root(int x) {
			int p = read(x).parent;
			return !p || (read(p).child[0] != x && read(p).child[1] != x);
		}
		void flip(int x) {
			if (!x) return;
			auto &v = write(x);
			std::swap(v.child[0], v.child[1]);
			if constexpr (!commutative) std::swap(v.aggregate, v.backward);
			v.reversed = !v.reversed;
		}
		void push(int x) {
			if (!read(x).reversed) return;
			flip(read(x).child[0]);
			flip(read(x).child[1]);
			write(x).reversed = false;
		}
		void rotate(int x) {
			int p = read(x).parent, g = read(p).parent;
			int d = read(p).child[1] == x, c = read(x).child[d ^ 1];
			if (!is_root(p)) write(g).child[read(g).child[1] == p] = x;
			write(x).parent = g;
			write(p).child[d] = c;
			if (c) write(c).parent = p;
			write(x).child[d ^ 1] = p;
			write(p).parent = x;
			pull(p);
			pull(x);
		}

	  public:
		Editor(PersistentLinkCutTree &owner, root_type version) : owner(owner), version(version) {
			assert(version <= owner.storage.node_count() && owner.touched.empty());
		}
		~Editor() {
			for (int x : owner.touched) {
				owner.cache[x].node.reset();
				owner.cache[x].dirty = false;
			}
			owner.touched.clear();
			owner.ancestors.clear();
		}
		const Node &read(int x) { return load(x); }
		Node &write(int x) {
			Node &value = load(x);
			owner.cache[x].dirty = true;
			return value;
		}
		root_type commit() {
			for (int x : owner.touched) if (owner.cache[x].dirty)
				version = owner.storage.set(version, x, std::move(*owner.cache[x].node));
			return version;
		}
		template<class T> result_type<T> finish(T value) { return {commit(), std::move(value)}; }
		void pull(int x) {
			auto &v = write(x);
			const auto &l = read(v.child[0]), &r = read(v.child[1]);
			v.count = l.count + r.count + 1;
			v.aggregate = op(op(l.aggregate, v.value), r.aggregate);
			if constexpr (!commutative) v.backward = op(op(r.backward, v.value), l.backward);
		}
		void splay(int x) {
			auto &path = owner.ancestors;
			path.clear();
			for (int y = x;; y = read(y).parent) {
				path.push_back(y);
				if (is_root(y)) break;
			}
			for (auto it = path.rbegin(); it != path.rend(); ++it) push(*it);
			while (!is_root(x)) {
				int p = read(x).parent, g = read(p).parent;
				if (!is_root(p)) rotate((read(p).child[0] == x) == (read(g).child[0] == p) ? p : x);
				rotate(x);
			}
		}
		int access(int x) {
			int last = 0;
			for (int y = x; y; y = read(y).parent) {
				splay(y);
				write(y).child[1] = last;
				if (last) write(last).parent = y;
				pull(y);
				last = y;
			}
			splay(x);
			return last;
		}
		void make_root(int x) { access(x); flip(x); }
		int root(int x) {
			access(x);
			push(x);
			while (read(x).child[0]) push(x = read(x).child[0]);
			splay(x);
			return x;
		}
		int expose(int u, int v) {
			make_root(u);
			access(v);
			assert(u == v || read(u).parent != 0);
			return v;
		}
		int select(int x, int k) {
			if (k < 0 || k >= read(x).count) return -1;
			for (;;) {
				push(x);
				int l = read(x).child[0], count = read(l).count;
				if (k == count) break;
				if (k < count) x = l;
				else k -= count + 1, x = read(x).child[1];
			}
			splay(x);
			return x - 1;
		}
	};

  public:
	explicit PersistentLinkCutTree(int n = 0, std::span<const std::pair<int, int>> edges = {})
		: PersistentLinkCutTree(initial_values(n), edges) {}
	explicit PersistentLinkCutTree(const std::vector<S> &values, std::span<const std::pair<int, int>> edges = {})
		: storage(initial_nodes(values, edges), Node(e())), cache(values.size() + 1) {}
	PersistentLinkCutTree(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree &operator=(const PersistentLinkCutTree &) = delete;
	PersistentLinkCutTree(PersistentLinkCutTree &&) = delete;
	PersistentLinkCutTree &operator=(PersistentLinkCutTree &&) = delete;
	int size() const { return storage.size() - 1; }
	bool empty() const { return size() == 0; }
	root_type initial_root() const { return storage.initial_root(); }
	S get(root_type version, int v) const { return storage.get(version, node(v)).value; }
	root_type set(root_type version, int v, S value) {
		Editor edit(*this, version);
		int x = node(v);
		edit.access(x);
		edit.write(x).value = std::move(value);
		edit.pull(x);
		return edit.commit();
	}
	root_type make_root(root_type version, int v) {
		Editor edit(*this, version);
		edit.make_root(node(v));
		return edit.commit();
	}
	root_type build_forest(root_type version, std::span<const std::pair<int, int>> edges) {
		auto parent = forest_parents(size(), edges);
		Editor edit(*this, version);
		for (int v = 0; v < size(); ++v) {
			int x = v + 1;
			Node replacement(edit.read(x).value);
			replacement.parent = parent[v] + 1;
			edit.write(x) = std::move(replacement);
		}
		return edit.commit();
	}
	result_type<int> root(root_type version, int v) {
		Editor edit(*this, version);
		return edit.finish(edit.root(node(v)) - 1);
	}
	result_type<bool> same(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(true);
		edit.access(u);
		edit.access(v);
		return edit.finish(edit.read(u).parent != 0);
	}
	result_type<bool> link(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(u).parent) return edit.finish(false);
		edit.write(u).parent = v;
		return edit.finish(true);
	}
	result_type<bool> cut(root_type version, int u, int v) {
		Editor edit(*this, version);
		u = node(u), v = node(v);
		if (u == v) return edit.finish(false);
		edit.make_root(u);
		edit.access(v);
		if (edit.read(v).child[0] != u || edit.read(u).child[1]) return edit.finish(false);
		edit.write(v).child[0] = 0;
		edit.write(u).parent = 0;
		edit.pull(v);
		return edit.finish(true);
	}
	result_type<S> prod(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).aggregate);
	}
	result_type<int> path_size(root_type version, int u, int v) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.read(x).count);
	}
	result_type<int> distance(root_type version, int u, int v) {
		auto result = path_size(version, u, v);
		--result.value;
		return result;
	}
	result_type<int> jump(root_type version, int u, int v, int k) {
		Editor edit(*this, version);
		int x = edit.expose(node(u), node(v));
		return edit.finish(edit.select(x, k));
	}
	result_type<int> lca(root_type version, int r, int u, int v) {
		Editor edit(*this, version);
		r = node(r), u = node(u), v = node(v);
		edit.make_root(r);
		edit.access(u);
		assert(r == u || edit.read(r).parent != 0);
		int w = edit.access(v);
		assert(u == v || edit.read(u).parent != 0);
		return edit.finish(w - 1);
	}
	void reserve(std::size_t count) { storage.reserve(count); }
	std::size_t node_count() const { return storage.node_count(); }
	std::size_t memory_usage() const {
		return storage.memory_usage() + cache.capacity() * sizeof(Slot)
			+ (touched.capacity() + ancestors.capacity()) * sizeof(int);
	}
};