1 点更新 パス Fold
(GraphTheory/VertexUpdatePathFold.hpp)

• View this file on GitHub
• Last update: 2022-05-29 18:12:58+09:00
• Include: #include "GraphTheory/VertexUpdatePathFold.hpp"
• Link: https://tkmst201.github.io/Library/GraphTheory/VertexUpdatePathFold.hpp

概要

頂点数 $N$ の木に対し、重軽分解 ( HL 分解) と セグメント木 とマージテクを用いて、$1$ 点更新とパスクエリを $\Theta(N)$ space $\mathcal(\log{N})$ time/query で処理します。
重軽分解 ( HL 分解) クエリ でも同様な処理ができますが、こちらの方が $\log$ が $1$ つ少ないです。
詳しくは使用例をご覧ください。

• VertexUpdatePathFold(const Graph &g, int root, bool VERTEX, const T &id_elem, const F &f)
  • $\Theta(N)$ 根 root の根付き木 g で初期化
• template<typename U> VertexUpdatePathFold(const Graph &g, int root, const std::vector&lt;U&gt; &dat, bool VERTEX, const T &id_elem, const F &f)
  • $\Theta(N)$ 根 root の根付き木 g と初期値 dat で初期化
• int size()
  • $\Theta(1)$ 頂点数 $N$ を返す
• int par(int v)
  • $\Theta(1)$ 頂点 $v$ の親を返す
• int depth(int v)
  • $\Theta(1)$ 頂点 $v$ の深さを返す
• void set(int v, const T & x)
  • $\Theta(\log{N})$ 頂点 $v$ に値 $x$ をセットする
• T get(int v)
  • $\Theta(1)$ 頂点 $v$ の値を返す
• void set(int u, int v, const T & x)
  • $\Theta(\log{N})$ 辺 $u-v$ に値 $x$ をセットする
• T get(int u, int v)
  • $\Theta(1)$ 辺 $u-v$ の値を返す
• T fold(int u, int v)
  • $\mathcal{O}(\log{N})$ $u-v$ パスを畳み込んだ結果を返す

コンストラクタ

以下、グラフの頂点数を $N$ とします。
F は二項演算 std::function<T (const T &, const T &)> の略記です。

制約

• $(T, f,$ id_elem$)$ はモノイド
• 頂点に値を持つ場合は VERTEX $= true$
• 辺に値を持つ場合は VERTEX $= false$

---

VertexUpdatePathFold(const Graph &g, int root, bool VERTEX, const T &id_elem, const F &f)

根が root の木 g で初期化します。 はじめ、すべての値は単位元です。

制約

• $0 \le$ root $< N$
• g は root を根とした根付き木または木

計算量

• $\Theta(N)$

---

template VertexUpdatePathFold(const Graph &g, int root, const std::vector<U> &dat, bool VERTEX, const T &id_elem, const F &f)

各頂点または辺の値を dat として根 root の木 g で初期化します。
辺 $u-v$ の値は $u$ と $v$ で深さが深い方の頂点の index に入れてください。

制約

• $0 \le$ root $< N$
• g は root を根とした根付き木または木

計算量

• $\Theta(N)$

---

メンバ関数

int size()

頂点数 $N$ を返します。

計算量

• $\Theta(1)$

---

int par(int v)

頂点 $v$ の親を返します。
親が存在しない場合ば $-1$ を返します。

計算量

• $\Theta(1)$

---

int depth(int v)

頂点 $v$ の深さ(root から $v$ までの単純パスに含まれる辺の数) を返します。

計算量

• $\Theta(1)$

---

void set(int v, const T & x)

頂点 $v$ に値 $x$ をセットします。

制約

• VERTEX $= true$
• $0 \leq v < N$

計算量

• $\Theta(\log{N})$

---

T get(int v)

頂点 $v$ の値を返します。

制約

• VERTEX $= true$
• $0 \leq v < N$

計算量

• $\Theta(1)$

---

void set(int u, int v, const T & x)

辺 $u-v$ に値 $x$ をセットします。

制約

• VERTEX $= false$
• $0 \leq u, v < N$

計算量

• $\Theta(\log{N})$

---

T get(int u, int v)

辺 $u-v$ の値を返します。

制約

• VERTEX $= false$
• $0 \leq u, v < N$

計算量

• $\Theta(1)$

---

T fold(int u, int v)

頂点 $u$ から頂点 $v$ へのパス上の頂点または辺を順にその値を並べたものを $a_1, a_2, \ldots, a_k$ として、$f(a_1, f(a_2, f(\ldots, f(a_{k-2}, a_{k-1}))\ldots)$ を返します。

制約

• $0 \leq u, v < N$

計算量

• $\mathcal{O}(\log{N})$

---

使用例

頂点に値を持つ例です。

#include <bits/stdc++.h>
#include "GraphTheory/VertexUpdatePathFold.hpp"
using namespace std;

int main() {
	using VUPF = VertexUpdatePathFold<int>;
	VUPF::Graph g(6);
	//         1(10)
	//    2(100)    3(1000)
	// 0(1)  4(10000)    5(100000)
	g[1].emplace_back(2);
	g[1].emplace_back(3);
	g[2].emplace_back(0);
	g[2].emplace_back(4);
	g[3].emplace_back(5);
	
	g[5].emplace_back(3); // 逆辺があっても良い
	
	vector<int> A{1, 10, 100, 1000, 10000, 100000};
	VUPF vupf(g, 1, A, true, 0, [](auto x, auto y) { return x + y; });
	
	// 1 -> 3 パス上の頂点 [1, 3] の総和
	cout << "fold(1, 3) = " << vupf.fold(1, 3) << endl; // 1010
	// 4 -> 5 パス上の頂点 [4, 2, 1, 3, 5] の総和
	cout << "fold(4, 5) = " << vupf.fold(4, 5) << endl; // 111110
	// 3 -> 3 パス上の頂点 [3] の総和
	cout << "fold(3, 3) = " << vupf.fold(3, 3) << endl; // 1000
	
	// 頂点 3 の値の変更
	vupf.set(3, 2000);
	// 1 -> 3 パス上の頂点 [1, 3] の総和
	cout << "fold(1, 3) = " << vupf.fold(1, 3) << endl; // 2010
	
	cout << "size() = " << vupf.size() << endl; // 6
	cout << "depth(3) = " << vupf.depth(3) << endl; // 1
	cout << "depth(1) = " << vupf.depth(1) << endl; // 0
	cout << "par(5) = " << vupf.par(5) << endl; // 3
	cout << "par(1) = " << vupf.par(1) << endl; // -1
}

辺に値を持つ例です。

#include <bits/stdc++.h>
#include "GraphTheory/VertexUpdatePathFold.hpp"
using namespace std;

int main() {
	using VUPF = VertexUpdatePathFold<int>;
	VUPF::Graph g(6);
	//         1(10)
	//    2(100)    3(1000)
	// 0(1)  4(10000)    5(100000)
	g[1].emplace_back(2);
	g[1].emplace_back(3);
	g[2].emplace_back(0);
	g[2].emplace_back(4);
	g[3].emplace_back(5);
	
	g[5].emplace_back(3); // 逆辺があっても良い
	
	vector<int> A({1, 10, 100, 1000, 10000, 100000});
	VUPF vupf(g, 1, A, false, 0, [](auto x, auto y) { return x + y; });
	vupf.set(1, 2, 100);
	vupf.set(1, 3, 1000);
	vupf.set(2, 0, 1);
	vupf.set(2, 4, 10000);
	vupf.set(3, 5, 100000);
	
	// 1 -> 3 パス上の辺 [1-3] の総和
	cout << "fold(1, 3) = " << vupf.fold(1, 3) << endl; // 1000
	// 4 -> 5 パス上の辺 [4-2, 2-1, 1-3, 3-5] の総和
	cout << "fold(4, 5) = " << vupf.fold(4, 5) << endl; // 111100
	// 3 -> 3 パス上の辺 [] の総和
	cout << "fold(3, 3) = " << vupf.fold(3, 3) << endl; // 0
}

解説

セグメントのマージテク

各 heavy-path (heavy-edge をつなげたパス) を二分木にすることを考える。
このとき、完全二分木ではなく、頂点の子孫に含まれるもとの木の頂点の数を重みとしてマージテクを行って作成する。
これにより、任意の頂点から根までの辺の本数は (light-edge の本数) + sum(heavy_path の木で上る辺) となる。
light-edge の辺の合計は HL 分解により $\mathcal{O}(\log{N})$ 本であり、第 2 項はマージテクにより打ち消し合って最終的に $\mathcal{O}(\log{N})$ になる。
詳しくは参考リンク先を読んで下さい。

実装メモ

実装の方針は、

1. 各部分木の頂点数を計算 sz[i] に格納
2. DFS の帰りがけ順で heavy-path をセグメント木に変形していく。

その他細かいテクニック

• sz[i] を用いて heavy-edge の index を計算したら一旦 nodes[i].par に保存しておく
• heavy-edge の index を計算し終えたら sz[i] は light-edge 以下の部分木の頂点数の合計を表すようにしている
• heavy_stk は作成中の heavy-path を表していて、負になった index が先頭を表している (つまり、light-edge を下りるときに負の index を追加し、heavy-edge を通るときに非負の index を入れている)
• merge_stk では、(l, r, p) で heavy_stk[l + st, r + st) の頂点のマージで全体の親を p とするように処理する。新たに作成された頂点の値は各部分木の値が確定したから計算されるようになっている
• uup, vup では、step=-1 のとき頂点が heavy-path セグメント木の葉にいることを仮定している (葉にいることと頂点がもとの木に含まれていることが同値)
• heavy[i] はもとの木に含まれる頂点 $i$ が属する heavy-path の番号を格納してあり、fold で同一のセグメント木にいるかの判定に使用している
• depth_[i] は fold で同一のセグメント木にいるときに、どちらの方向に heavy-path の値を回収すれば良いかの判定に使用している

デバッグ用メモ

各ノードの情報が正しいかおおまかにチェックします。

void tree_check() const noexcept {
	int top = 0;
	while (nodes[top].par < nodes.size()) top = nodes[top].par;
	std::vector<std::pair<int, int>> chd(nodes.size(), {-1, -1});
	for (int i = 0; i < n; ++i) {
		assert(nodes[i].childs[0] == -1);
		assert(nodes[i].childs[1] == -1);
		if (i == top) continue;
		const int p = nodes[i].par;
		if (nodes[p].childs[0] == i) chd[p].first = i;
		else if (nodes[p].childs[1] == i) chd[p].second = i;
		else chd[p].first = i;
	}
	for (int i = n; i < nodes.size(); ++i) {
		assert(nodes[i].childs[0] != -1);
		assert(nodes[i].childs[1] != -1);
		assert(f(nodes[nodes[i].childs[0]].val, nodes[nodes[i].childs[1]].val) == nodes[i].val);
		assert(f(nodes[nodes[i].childs[1]].rval, nodes[nodes[i].childs[0]].rval) == nodes[i].rval);
		if (i == top) continue;
		const int p = nodes[i].par;
		if (nodes[p].childs[0] == i) chd[p].first = i;
		else if (nodes[p].childs[1] == i) chd[p].second = i;
		else chd[p].first = i;
	}
	for (int i = n; i < nodes.size(); ++i) {
		assert(chd[i].first != -1);
		assert(chd[i].second != -1);
		auto [l, r] = nodes[i].childs;
		assert(l == chd[i].first);
		assert(r == chd[i].second);
		
		assert(nodes[l].decomp_dep() == nodes[r].decomp_dep());
		assert(nodes[l].decomp_dep().second == nodes[i].decomp_dep().second);
		assert(nodes[l].decomp_dep().first == nodes[i].decomp_dep().first + 1);
		if (i == top) continue;
		const int p = nodes[i].par;
		if (p < n) {
			assert(nodes[i].decomp_dep().first == 0);
			assert(nodes[p].decomp_dep().second == nodes[i].decomp_dep().second - 1);
		}
	}
	int mxd = 0;
	for (int i = 0; i < n; ++i) {
		int u = i;
		int cnt = 0;
		for (; nodes[u].par < nodes.size(); u = nodes[u].par, ++cnt);
		if (mxd < cnt) mxd = cnt;
	}
	
	int lgn = 1;
	while ((1 << lgn) < n) ++lgn;
	assert(mxd < 5 * lgn);
}

TODO

• TODO: 辺に値を載せた場合の verify

参考

2022/05/28: https://www.mathenachia.blog/mergetech-and-logn/
2022/05/28: https://yosupo.hatenablog.com/entry/2015/10/02/233244
2022/05/28: 計算量解析 https://noshi91.hatenablog.com/entry/2022/03/27/042143

Verified with

• Test/VertexUpdatePathFold.vertex.test.cpp

Code

#ifndef INCLUDE_GUARD_VERTEX_UPDATE_PATH_FOLD_HPP
#define INCLUDE_GUARD_VERTEX_UPDATE_PATH_FOLD_HPP

#include <algorithm>
#include <cassert>
#include <functional>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/VertexUpdatePathFold.hpp
 */
template<typename T>
struct VertexUpdatePathFold {
	using value_type = T;
	using const_reference = const value_type &;
	using Graph = std::vector<std::vector<int>>;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	using int3 = std::tuple<int, int, int>;
	struct Node {
		value_type val, rval;
		int par;
		int dep; // 16bits(seg depth) 16bits(heavy-path depth)

		int childs[2];
		Node() = default;
		Node(value_type val) : val(val), rval(val), par(-1), childs{-1, -1} {};
		Node(int par, int seg_dep, int heavy_dep) : par(par), dep(comp_dep(seg_dep, heavy_dep)) {}
		Node(int par, int seg_dep, int heavy_dep, int lcld, int rcld)
			: par(par), dep(comp_dep(seg_dep, heavy_dep)), childs{lcld, rcld} {}
		static int comp_dep(int seg_dep, int heavy_dep) noexcept {
			return seg_dep << 16 | heavy_dep;
		}
		std::pair<int, int> decomp_dep() const noexcept {
			return {dep >> 16, dep & ((1 << 16) - 1)};
		}
		void set_dep(int seg_dep, int heavy_dep) noexcept {
			dep = comp_dep(seg_dep, heavy_dep);
		}
		void set_prop(int par, int seg_dep, int heavy_dep) noexcept {
			this->par = par;
			set_dep(seg_dep, heavy_dep);
		}
	};
	
	int n;
	const bool VERTEX;
	value_type id_elem;
	F f;
	std::vector<Node> nodes;
	std::vector<int> par_, depth_, heavy;
	
	void node_calc(int u) {
		nodes[u].val = f(nodes[nodes[u].childs[0]].val, nodes[nodes[u].childs[1]].val);
		nodes[u].rval = f(nodes[nodes[u].childs[1]].rval, nodes[nodes[u].childs[0]].rval);
	}
	
public:
	VertexUpdatePathFold(const Graph &g, int root, bool VERTEX, const_reference d_elem, const F &f)
		: n(g.size()), VERTEX(VERTEX), id_elem(id_elem), f(f) {
		nodes.reserve(2 * n);
		nodes.assign(n, {id_elem});
		build(g, root);
	}
	
	template<typename U>
	VertexUpdatePathFold(const Graph &g, int root, const std::vector<U> &dat, bool VERTEX, const_reference id_elem, const F &f)
		: n(g.size()), VERTEX(VERTEX), id_elem(id_elem), f(f) {
		nodes.reserve(2 * n);
		for (int i = 0; i < n; ++i) nodes.emplace_back(dat[i]);
		build(g, root);
	}
	
private:
	void build(const Graph &g, int root) {
		par_.assign(n, -1);
		depth_.assign(n, 0);
		heavy.assign(n, -1);
		std::vector<int> siz(n, 0);
		std::stack<std::pair<int, int>> stk;
		stk.emplace(root, 0);
		siz[root] = 0;
		while (stk.size()) {
			auto [u, idx] = stk.top(); stk.pop();
			if (idx == g[u].size()) {
				if (par_[u] != -1) siz[par_[u]] += ++siz[u];
			}
			else {
				stk.emplace(u, idx + 1);
				const int v = g[u][idx];
				if (v == par_[u]) continue;
				stk.emplace(v, 0);
				par_[v] = u;
				depth_[v] = depth_[u] + 1;
			}
		}
		int heavy_num = 0;
		std::vector<int> heavy_stk;
		heavy_stk.emplace_back(-(root + 1));
		nodes[root].dep = 0;
		stk.emplace(root, 0);
		while (stk.size()) {
			auto [u, idx] = stk.top(); stk.pop();
			if (idx == g[u].size()) {
				if (nodes[u].par != -1) {
					const int v = g[u][nodes[u].par];
					heavy_stk.emplace_back(v);
					nodes[v].dep = nodes[u].dep;
					stk.emplace(v, 0);
					continue;
				}
				if (g[u].size() == 0) siz[u] = 1;
				int st = static_cast<int>(heavy_stk.size()) - 1;
				while (heavy_stk[st] >= 0) --st;
				heavy_stk[st] = -heavy_stk[st] - 1;
				const int rootnum = n << 1;
				const int heavy_par = st == 0 ? rootnum : (heavy_stk[st - 1] >= 0 ? heavy_stk[st - 1] : -heavy_stk[st - 1] - 1);
				const int hs = static_cast<int>(heavy_stk.size()) - st;
				const int heavy_dep = nodes[heavy_stk[st]].dep;
				for (int i = 0; i < hs; ++i) heavy[heavy_stk[st + i]] = heavy_num;
				++heavy_num;
				std::vector<int> sum(hs + 1);
				sum[0] = 0;
				for (int i = 0; i < hs; ++i) sum[i + 1] = sum[i] + siz[heavy_stk[st + i]];
				std::stack<int3> merge_stk;
				merge_stk.emplace(0, hs, heavy_par);
				while (merge_stk.size()) {
					auto [l, r, p] = merge_stk.top(); merge_stk.pop();
					if (l == -1) { node_calc(p); continue; }
					const bool rchild = p < 0;
					if (p < 0) p = -p - 1;
					const int seg_dep = (p == heavy_par) ? 0 : nodes[p].decomp_dep().first + 1;
					auto merge = [&](int u, int v, int p, bool rchild, int seg_dep) -> int {
						const int self = nodes.size();
						nodes.emplace_back(p, seg_dep, heavy_dep, u, v);
						if (u != -1) nodes[u].set_prop(self, seg_dep + 1, heavy_dep);
						if (v != -1) nodes[v].set_prop(self, seg_dep + 1, heavy_dep);
						if (p != heavy_par) nodes[p].childs[rchild] = self;
						if (u != -1 && v != -1) node_calc(self);
						else merge_stk.emplace(-1, -1, self);
						return self;
					};
					if (r - l <= 2) {
						if (r - l == 1) {
							const int v = heavy_stk[l + st];
							nodes[v].set_prop(p, seg_dep, heavy_dep);
							if (p != heavy_par) nodes[p].childs[rchild] = v;
						}
						else merge(heavy_stk[l + st], heavy_stk[l + st + 1], p, rchild, seg_dep);
						continue;
					}
					const int m = lower_bound(sum.begin() + l + 1, sum.begin() + r + 1, (sum[r] + sum[l]) >> 1) - sum.begin() - 1;
					const int v = heavy_stk[m + st];
					const int top = nodes.size();
					if (m == l) {
						merge(v, -1, p, rchild, seg_dep);
						merge_stk.emplace(m + 1, r, -top - 1);
					}
					else if (m + 1 == r) {
						merge(-1, v, p, rchild, seg_dep);
						merge_stk.emplace(l, m, top);
					}
					else {
						if (sum[m] - sum[l] < sum[r] - sum[m + 1]) {
							merge(-1, -1, p, rchild, seg_dep);
							merge_stk.emplace(m + 1, r, -top - 1);
							merge(-1, v, top, false, seg_dep + 1);
							merge_stk.emplace(l, m, top + 1);
						}
						else {
							merge(-1, -1, p, rchild, seg_dep);
							merge_stk.emplace(l, m, top);
							merge(v, -1, top, true, seg_dep + 1);
							merge_stk.emplace(m + 1, r, -(top + 1) - 1);
						}
					}
				}
				while (heavy_stk.size() > st) heavy_stk.pop_back();
				if (heavy_par != rootnum) siz[heavy_par] += hs;
			}
			else {
				if (idx == 0) {
					siz[u] = 1;
					int mxc = 0;
					for (int i = 0; i < static_cast<int>(g[u].size()); ++i) {
						const int v = g[u][i];
						if (v != par_[u] && mxc < siz[v]) {
							nodes[u].par = i;
							mxc = siz[v];
						}
					}
				}
				stk.emplace(u, idx + 1);
				const int v = g[u][idx];
				if (v == par_[u] || idx == nodes[u].par) continue;
				heavy_stk.emplace_back(-(v + 1));
				nodes[v].dep = nodes[u].dep + 1;
				stk.emplace(v, 0);
			}
		}
	}

public:
	int size() const noexcept {
		return n;
	}
	
	int par(int v) const noexcept {
		assert(0 <= v && v < n);
		return par_[v];
	}
	
	int depth(int v) const noexcept {
		assert(0 <= v && v < n);
		return depth_[v];
	}
	
	void set(int v, const_reference x) noexcept {
		assert(VERTEX);
		assert(0 <= v && v < n);
		set_impl(v, x);
	}
	
	value_type get(int v) const noexcept {
		assert(VERTEX);
		assert(0 <= v && v < n);
		return get_impl(v);
	}
	
	void set(int u, int v, const_reference x) noexcept {
		assert(!VERTEX);
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		set_impl(par_[u] == v ? u : v, x);
	}
	
	value_type get(int u, int v) const noexcept {
		assert(!VERTEX);
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		return get_impl(par_[u] == v ? u : v);
	}
	
	value_type fold(int u, int v) const noexcept {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		value_type lv = id_elem, rv = id_elem;
		auto uup = [&](int step = -1, bool lret = true) {
			if (step == -1) {
				lv = f(lv, nodes[u].rval);
				step = nodes[u].decomp_dep().first + 1;
			}
			while (step--) {
				const int p = nodes[u].par;
				if (lret && nodes[p].childs[1] == u) lv = f(lv, nodes[nodes[p].childs[0]].rval);
				if (!lret && nodes[p].childs[0] == u) lv = f(lv, nodes[nodes[p].childs[1]].val);
				u = p;
			}
		};
		auto vup = [&](int step = -1, bool lret = true) {
			if (step == -1) {
				rv = f(nodes[v].val, rv);
				step = nodes[v].decomp_dep().first + 1;
			}
			while(step--) {
				const int p = nodes[v].par;
				if (lret && nodes[p].childs[1] == v) rv = f(nodes[nodes[p].childs[0]].val, rv);
				if (!lret && nodes[p].childs[0] == v) rv = f(nodes[nodes[p].childs[1]].rval, rv);
				v = p;
			}
		};
		while (nodes[u].decomp_dep().second > nodes[v].decomp_dep().second) uup();
		while (nodes[u].decomp_dep().second < nodes[v].decomp_dep().second) vup();
		while (heavy[u] != heavy[v]) uup(), vup();
		bool lright = depth_[u] > depth_[v];
		if (u == v) return VERTEX ? f(f(lv, nodes[u].val), rv) : f(lv, rv);
		if (VERTEX || lright) lv = f(lv, nodes[u].val);
		if (VERTEX || !lright) rv = f(nodes[v].val, rv);
		const int udep = nodes[u].decomp_dep().first, vdep = nodes[v].decomp_dep().first;
		if (udep > vdep) uup(udep - vdep, lright);
		if (udep < vdep) vup(vdep - udep, !lright);
		while (nodes[u].par != nodes[v].par) uup(1, lright), vup(1, !lright);
		return f(lv, rv);
	}
	
private:
	void set_impl(int v, const_reference x) noexcept {
		nodes[v].val = x;
		nodes[v].rval = x;
		for (int i = nodes[v].decomp_dep().first; i > 0; --i) node_calc(v = nodes[v].par);
	}
	
	value_type get_impl(int v) const noexcept {
		return nodes[v].val;
	}
};

#endif // INCLUDE_GUARD_VERTEX_UPDATE_PATH_FOLD_HPP

#line 1 "GraphTheory/VertexUpdatePathFold.hpp"



#include <algorithm>
#include <cassert>
#include <functional>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/VertexUpdatePathFold.hpp
 */
template<typename T>
struct VertexUpdatePathFold {
	using value_type = T;
	using const_reference = const value_type &;
	using Graph = std::vector<std::vector<int>>;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	using int3 = std::tuple<int, int, int>;
	struct Node {
		value_type val, rval;
		int par;
		int dep; // 16bits(seg depth) 16bits(heavy-path depth)

		int childs[2];
		Node() = default;
		Node(value_type val) : val(val), rval(val), par(-1), childs{-1, -1} {};
		Node(int par, int seg_dep, int heavy_dep) : par(par), dep(comp_dep(seg_dep, heavy_dep)) {}
		Node(int par, int seg_dep, int heavy_dep, int lcld, int rcld)
			: par(par), dep(comp_dep(seg_dep, heavy_dep)), childs{lcld, rcld} {}
		static int comp_dep(int seg_dep, int heavy_dep) noexcept {
			return seg_dep << 16 | heavy_dep;
		}
		std::pair<int, int> decomp_dep() const noexcept {
			return {dep >> 16, dep & ((1 << 16) - 1)};
		}
		void set_dep(int seg_dep, int heavy_dep) noexcept {
			dep = comp_dep(seg_dep, heavy_dep);
		}
		void set_prop(int par, int seg_dep, int heavy_dep) noexcept {
			this->par = par;
			set_dep(seg_dep, heavy_dep);
		}
	};
	
	int n;
	const bool VERTEX;
	value_type id_elem;
	F f;
	std::vector<Node> nodes;
	std::vector<int> par_, depth_, heavy;
	
	void node_calc(int u) {
		nodes[u].val = f(nodes[nodes[u].childs[0]].val, nodes[nodes[u].childs[1]].val);
		nodes[u].rval = f(nodes[nodes[u].childs[1]].rval, nodes[nodes[u].childs[0]].rval);
	}
	
public:
	VertexUpdatePathFold(const Graph &g, int root, bool VERTEX, const_reference d_elem, const F &f)
		: n(g.size()), VERTEX(VERTEX), id_elem(id_elem), f(f) {
		nodes.reserve(2 * n);
		nodes.assign(n, {id_elem});
		build(g, root);
	}
	
	template<typename U>
	VertexUpdatePathFold(const Graph &g, int root, const std::vector<U> &dat, bool VERTEX, const_reference id_elem, const F &f)
		: n(g.size()), VERTEX(VERTEX), id_elem(id_elem), f(f) {
		nodes.reserve(2 * n);
		for (int i = 0; i < n; ++i) nodes.emplace_back(dat[i]);
		build(g, root);
	}
	
private:
	void build(const Graph &g, int root) {
		par_.assign(n, -1);
		depth_.assign(n, 0);
		heavy.assign(n, -1);
		std::vector<int> siz(n, 0);
		std::stack<std::pair<int, int>> stk;
		stk.emplace(root, 0);
		siz[root] = 0;
		while (stk.size()) {
			auto [u, idx] = stk.top(); stk.pop();
			if (idx == g[u].size()) {
				if (par_[u] != -1) siz[par_[u]] += ++siz[u];
			}
			else {
				stk.emplace(u, idx + 1);
				const int v = g[u][idx];
				if (v == par_[u]) continue;
				stk.emplace(v, 0);
				par_[v] = u;
				depth_[v] = depth_[u] + 1;
			}
		}
		int heavy_num = 0;
		std::vector<int> heavy_stk;
		heavy_stk.emplace_back(-(root + 1));
		nodes[root].dep = 0;
		stk.emplace(root, 0);
		while (stk.size()) {
			auto [u, idx] = stk.top(); stk.pop();
			if (idx == g[u].size()) {
				if (nodes[u].par != -1) {
					const int v = g[u][nodes[u].par];
					heavy_stk.emplace_back(v);
					nodes[v].dep = nodes[u].dep;
					stk.emplace(v, 0);
					continue;
				}
				if (g[u].size() == 0) siz[u] = 1;
				int st = static_cast<int>(heavy_stk.size()) - 1;
				while (heavy_stk[st] >= 0) --st;
				heavy_stk[st] = -heavy_stk[st] - 1;
				const int rootnum = n << 1;
				const int heavy_par = st == 0 ? rootnum : (heavy_stk[st - 1] >= 0 ? heavy_stk[st - 1] : -heavy_stk[st - 1] - 1);
				const int hs = static_cast<int>(heavy_stk.size()) - st;
				const int heavy_dep = nodes[heavy_stk[st]].dep;
				for (int i = 0; i < hs; ++i) heavy[heavy_stk[st + i]] = heavy_num;
				++heavy_num;
				std::vector<int> sum(hs + 1);
				sum[0] = 0;
				for (int i = 0; i < hs; ++i) sum[i + 1] = sum[i] + siz[heavy_stk[st + i]];
				std::stack<int3> merge_stk;
				merge_stk.emplace(0, hs, heavy_par);
				while (merge_stk.size()) {
					auto [l, r, p] = merge_stk.top(); merge_stk.pop();
					if (l == -1) { node_calc(p); continue; }
					const bool rchild = p < 0;
					if (p < 0) p = -p - 1;
					const int seg_dep = (p == heavy_par) ? 0 : nodes[p].decomp_dep().first + 1;
					auto merge = [&](int u, int v, int p, bool rchild, int seg_dep) -> int {
						const int self = nodes.size();
						nodes.emplace_back(p, seg_dep, heavy_dep, u, v);
						if (u != -1) nodes[u].set_prop(self, seg_dep + 1, heavy_dep);
						if (v != -1) nodes[v].set_prop(self, seg_dep + 1, heavy_dep);
						if (p != heavy_par) nodes[p].childs[rchild] = self;
						if (u != -1 && v != -1) node_calc(self);
						else merge_stk.emplace(-1, -1, self);
						return self;
					};
					if (r - l <= 2) {
						if (r - l == 1) {
							const int v = heavy_stk[l + st];
							nodes[v].set_prop(p, seg_dep, heavy_dep);
							if (p != heavy_par) nodes[p].childs[rchild] = v;
						}
						else merge(heavy_stk[l + st], heavy_stk[l + st + 1], p, rchild, seg_dep);
						continue;
					}
					const int m = lower_bound(sum.begin() + l + 1, sum.begin() + r + 1, (sum[r] + sum[l]) >> 1) - sum.begin() - 1;
					const int v = heavy_stk[m + st];
					const int top = nodes.size();
					if (m == l) {
						merge(v, -1, p, rchild, seg_dep);
						merge_stk.emplace(m + 1, r, -top - 1);
					}
					else if (m + 1 == r) {
						merge(-1, v, p, rchild, seg_dep);
						merge_stk.emplace(l, m, top);
					}
					else {
						if (sum[m] - sum[l] < sum[r] - sum[m + 1]) {
							merge(-1, -1, p, rchild, seg_dep);
							merge_stk.emplace(m + 1, r, -top - 1);
							merge(-1, v, top, false, seg_dep + 1);
							merge_stk.emplace(l, m, top + 1);
						}
						else {
							merge(-1, -1, p, rchild, seg_dep);
							merge_stk.emplace(l, m, top);
							merge(v, -1, top, true, seg_dep + 1);
							merge_stk.emplace(m + 1, r, -(top + 1) - 1);
						}
					}
				}
				while (heavy_stk.size() > st) heavy_stk.pop_back();
				if (heavy_par != rootnum) siz[heavy_par] += hs;
			}
			else {
				if (idx == 0) {
					siz[u] = 1;
					int mxc = 0;
					for (int i = 0; i < static_cast<int>(g[u].size()); ++i) {
						const int v = g[u][i];
						if (v != par_[u] && mxc < siz[v]) {
							nodes[u].par = i;
							mxc = siz[v];
						}
					}
				}
				stk.emplace(u, idx + 1);
				const int v = g[u][idx];
				if (v == par_[u] || idx == nodes[u].par) continue;
				heavy_stk.emplace_back(-(v + 1));
				nodes[v].dep = nodes[u].dep + 1;
				stk.emplace(v, 0);
			}
		}
	}

public:
	int size() const noexcept {
		return n;
	}
	
	int par(int v) const noexcept {
		assert(0 <= v && v < n);
		return par_[v];
	}
	
	int depth(int v) const noexcept {
		assert(0 <= v && v < n);
		return depth_[v];
	}
	
	void set(int v, const_reference x) noexcept {
		assert(VERTEX);
		assert(0 <= v && v < n);
		set_impl(v, x);
	}
	
	value_type get(int v) const noexcept {
		assert(VERTEX);
		assert(0 <= v && v < n);
		return get_impl(v);
	}
	
	void set(int u, int v, const_reference x) noexcept {
		assert(!VERTEX);
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		set_impl(par_[u] == v ? u : v, x);
	}
	
	value_type get(int u, int v) const noexcept {
		assert(!VERTEX);
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		return get_impl(par_[u] == v ? u : v);
	}
	
	value_type fold(int u, int v) const noexcept {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		value_type lv = id_elem, rv = id_elem;
		auto uup = [&](int step = -1, bool lret = true) {
			if (step == -1) {
				lv = f(lv, nodes[u].rval);
				step = nodes[u].decomp_dep().first + 1;
			}
			while (step--) {
				const int p = nodes[u].par;
				if (lret && nodes[p].childs[1] == u) lv = f(lv, nodes[nodes[p].childs[0]].rval);
				if (!lret && nodes[p].childs[0] == u) lv = f(lv, nodes[nodes[p].childs[1]].val);
				u = p;
			}
		};
		auto vup = [&](int step = -1, bool lret = true) {
			if (step == -1) {
				rv = f(nodes[v].val, rv);
				step = nodes[v].decomp_dep().first + 1;
			}
			while(step--) {
				const int p = nodes[v].par;
				if (lret && nodes[p].childs[1] == v) rv = f(nodes[nodes[p].childs[0]].val, rv);
				if (!lret && nodes[p].childs[0] == v) rv = f(nodes[nodes[p].childs[1]].rval, rv);
				v = p;
			}
		};
		while (nodes[u].decomp_dep().second > nodes[v].decomp_dep().second) uup();
		while (nodes[u].decomp_dep().second < nodes[v].decomp_dep().second) vup();
		while (heavy[u] != heavy[v]) uup(), vup();
		bool lright = depth_[u] > depth_[v];
		if (u == v) return VERTEX ? f(f(lv, nodes[u].val), rv) : f(lv, rv);
		if (VERTEX || lright) lv = f(lv, nodes[u].val);
		if (VERTEX || !lright) rv = f(nodes[v].val, rv);
		const int udep = nodes[u].decomp_dep().first, vdep = nodes[v].decomp_dep().first;
		if (udep > vdep) uup(udep - vdep, lright);
		if (udep < vdep) vup(vdep - udep, !lright);
		while (nodes[u].par != nodes[v].par) uup(1, lright), vup(1, !lright);
		return f(lv, rv);
	}
	
private:
	void set_impl(int v, const_reference x) noexcept {
		nodes[v].val = x;
		nodes[v].rval = x;
		for (int i = nodes[v].decomp_dep().first; i > 0; --i) node_calc(v = nodes[v].par);
	}
	
	value_type get_impl(int v) const noexcept {
		return nodes[v].val;
	}
};

Back to top page