Static Top Tree

tree/static_top_tree.hpp · GitHub で見る

共通ページ

木の形を固定したまま、頂点・辺の値の変更に合わせて木 DP を更新します。構築済みの HLD と、DP の型・演算を渡します。

#include "lib/tree/static_top_tree.hpp"

struct SumDP {
	using Vertex = long long;
	using Point = long long;
	using Path = long long;
	static Point point_identity() { return 0; }
	static Path path_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; }
};

HLD tree(3);
tree.add_edge(0, 1);
tree.add_edge(1, 2);
tree.build(0);
StaticTopTree<SumDP> dp(tree, {1, 2, 3});
dp.set(1, 4);
long long total = dp.dp();                  // 8
long long subtree = dp.subtree_prod(1);     // 7

操作	内容・返り値	計算量
`StaticTopTree<DP>()`	空の木を作る	\(O(1)\)
`StaticTopTree<DP>(tree,values)`	構築済みの HLD と頂点番号順の `vector<Vertex>` で構築	\(O(n\log n)\)
`build(tree,values)`	木と値を置き換えて再構築	\(O(n\log n)\)
`size()` / `empty()`	頂点数／空か	\(O(1)\)
`root()`	構築時の根。空なら `-1`	\(O(1)\)
`parent(v)`	元の木の親。根では `-1`	\(O(1)\)
`edge_vertex(e)`	HLD に追加した辺 ID `e` の子側の頂点	\(O(1)\)
`get(v)`	頂点 `v` の `const Vertex&`	\(O(1)\)
`set(v,value)`	頂点の値を変更し、必要なクラスタを更新	\(O(\log n)\)
`all_prod()`	木全体の `Path`。境界のパスは構築時の根から heavy path の末尾まで	\(O(1)\)
`dp()`	`DP::add_edge(all_prod())` による木全体の `Point`	\(O(1)\)
`subtree_prod(v)`	構築時の根に対する `v` の部分木の `Path`。境界のパスは `v` から heavy path の末尾まで	\(O(\log n)\)
`prod(v)`	木全体を、構築時の根から `v` へのパスに沿って集約した `Path`	\(O(\log n)\)
`Vertex` / `Point` / `Path`	`DP` に指定した型の別名	—（型）

頂点は 0 始まりです。空の木・1 頂点の木も扱います。values.size() は頂点数と一致させます。構築時に必要な情報をコピーするため、元の HLD は構築後に破棄できます。辺の追加・削除には再構築が必要です。get の参照は再構築で無効になります。

DP には次の型と static 関数を定義します。値はコピー・代入可能な型にします。

型・関数	意味	計算量
`DP::Vertex`	頂点の情報。必要なら親辺の情報も含める	—（型）
`DP::Point`	同じ親へ接続する枝の集約	—（型）
`DP::Path`	境界のパスを持つクラスタの集約	—（型）
`DP::point_identity()`	枝がない場合の `Point`	DP による（定数時間を仮定）
`DP::path_identity()`	空のパスの `Path`	DP による（定数時間を仮定）
`DP::rake(a,b)`	同じ親へ接続する枝を併合	DP による（定数時間を仮定）
`DP::compress(a,b)`	上側のパス `a` と下側のパス `b` をこの順で連結	DP による（定数時間を仮定）
`DP::add_edge(path)`	パスクラスタを親へ接続する枝の `Point` に変換	DP による（定数時間を仮定）
`DP::add_vertex(point,vertex)`	枝の集約に頂点を加え、長さ 1 の `Path` に変換	DP による（定数時間を仮定）

rake は可換モノイド、compress はモノイドにします。add_edge(path_identity()) == point_identity() が必要です。クラスタの併合順序によらず同じ木 DP を表すように各演算を定義します。逆元は不要で、積が 0 になる DP も扱えます。

辺を更新する場合は、子の Vertex に親辺の値を保存し、edge_vertex(e) で子を求めて set します。根の仮想的な親辺は、DP に応じた単位元にします。subtree_prod(v) にも Vertex に保存した v の親辺の作用が含まれます。

prod(v) は経路上の頂点だけを集約する操作ではありません。経路外の枝を Point として畳み、全頂点を含む根から v へのクラスタを返します。Path に両方向の情報を持たせれば、指定した頂点を根とする全方位の値も取り出せます。逆方向の辺・頂点の作用も DP 側で定義します。一次関数合成の全方位 DP と可変根の使用例を参照してください。独立集合のように枝の方向を反転させる処理が必要な DP では、固定根の Path をそのまま逆順にするだけでは全方位の答えになりません。

all_prod・subtree_prod も Path を返すため、固定根の答えとして使う際には DP に応じた取り出し方を使います。例えば行列を Path にする DP では、末尾に空の子の状態を作用させます。dp はその処理を add_edge で行う場合に使えます。

DP の型・演算を定数時間・定数空間とすると、HLD 構築後の構築・再構築は \(O(n\log n)\) 時間、空間は \(O(n)\) です。set・subtree_prod・prod は \(O(\log n)\)、それ以外の操作は \(O(1)\) です。

依存ライブラリ

検証コード

コード

#line 1 "tree/static_top_tree.hpp"

#include <cassert>
#include <utility>
#include <vector>
#line 1 "components/static_top_tree_structure.hpp"

#include <algorithm>
#line 6 "components/static_top_tree_structure.hpp"
#include <functional>
#include <limits>
#line 1 "tree/hld.hpp"

#line 5 "tree/hld.hpp"
#include <array>
#line 7 "tree/hld.hpp"
#include <cstddef>
#line 11 "tree/hld.hpp"

class HLD {
	int shape_ = 0, center_ = 0;
	struct Node { int position, head, parent, offset; };
	std::vector<Node> nodes;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < n && int(in.size()) == n); }

void initialize() {
		depth.assign(n, 0);
		size.assign(n, 1);
		heavy.assign(n, -1);
		head.resize(n), in.resize(n), out.resize(n), order.resize(n);
		nodes.resize(n);
		shape_ = center_ = 0;
	}
	void finish(int root) {
		in[root] = 0, out[root] = n, head[root] = root;
		for (int i = n - 2; i >= 0; --i) {
			int v = order[i], p = parent[v];
			depth[v] = depth[p] + 1;
			if (heavy[p] == v) in[v] = in[p] + 1, head[v] = head[p];
			else in[v] = out[p] -= size[v], head[v] = v;
			out[v] = in[v] + size[v];
		}
		for (int v = 0; v < n; ++v) out[v] = in[v] + size[v], order[in[v]] = v;
		parent[root] = -1;
		for (int v = 0; v < n; ++v) nodes[v] = {in[v], in[head[v]], parent[head[v]], depth[v] - in[v]};
	}

public:
	struct Segment {
		int l, r;
		bool reversed;
	};
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> parent, depth, size, heavy, head, in, out, order;
	explicit HLD(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
		edges.reserve(std::max(0, n - 1));
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		edges.emplace_back(u, v);
		return int(edges.size()) - 1;
	}
	void build(int root = 0) {
		assert(n >= 0 && edges.size() == std::size_t(std::max(0, n - 1)));
		assert(!n || (0 <= root && root < n));
		parent.assign(n, -1);
		initialize();
		if (!n) return;
		std::vector<int> degree(n), neighbors(n);
		for (auto [u, v] : edges) {
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		center_ = int(std::max_element(degree.begin(), degree.end()) - degree.begin());
		shape_ = degree[center_] <= 2 ? 1 : degree[center_] == n - 1 ? 2 : 0;
		degree[root] += 2;
		int count = 0;
		for (int v = 0; v < n; ++v) if (degree[v] == 1) order[count++] = v;
		for (int i = 0; i < count; ++i) {
			int v = order[i], p = neighbors[v];
			parent[v] = p;
			size[p] += size[v];
			if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
			neighbors[p] ^= v;
			if (--degree[p] == 1) order[count++] = p;
		}
		assert(count == n - 1);
		finish(root);
	}
	void build_from_parents(std::vector<int> parents) {
		assert(parents.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		n = static_cast<int>(parents.size());
		parent = std::move(parents);
		initialize();
		edges.clear();
		edges.reserve(std::max(0, n - 1));
		if (!n) return;
		std::fill(out.begin(), out.end(), 0);
		int root = -1;
		bool ordered = true;
		for (int v = 0; v < n; ++v) {
			int p = parent[v];
			assert(-1 <= p && p < n && p != v);
			if (p == -1) {
				assert(root == -1);
				root = v;
			} else {
				++out[p];
				edges.emplace_back(p, v);
				ordered &= p < v;
			}
		}
		assert(root != -1);
		int maximum = 0;
		for (int v = 0; v < n; ++v) {
			int degree = out[v] + (v != root);
			if (degree > maximum) maximum = degree, center_ = v;
		}
		shape_ = maximum <= 2 ? 1 : maximum == n - 1 ? 2 : 0;
		if (ordered) {
			for (int v = n - 1; v > 0; --v) {
				int p = parent[v];
				size[p] += size[v];
				if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
				order[n - 1 - v] = v;
			}
		} else {
			int count = 0;
			for (int v = 0; v < n; ++v) if (!out[v] && v != root) order[count++] = v;
			for (int i = 0; i < count; ++i) {
				int v = order[i], p = parent[v];
				size[p] += size[v];
				if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
				if (!--out[p] && p != root) order[count++] = p;
			}
			assert(count == n - 1);
		}
		finish(root);
	}
	int lca(int u, int v) const {
		check(u), check(v);
		if (shape_ == 1) return head[u] != head[v] ? order[0] : in[u] < in[v] ? u : v;
		if (shape_ == 2) return u == v ? u : u == order[0] || v == order[0] ? order[0] : center_;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) u = nodes[u].parent;
			else v = nodes[v].parent;
		}
		return nodes[u].position < nodes[v].position ? u : v;
	}
	int dist(int u, int v) const {
		int w = lca(u, v);
		return depth[u] + depth[v] - 2 * depth[w];
	}
	bool is_ancestor(int u, int v) const {
		check(u), check(v);
		return in[u] <= in[v] && in[v] < out[u];
	}
	int ancestor(int v, int k) const {
		check(v);
		if (shape_) {
			if (k < 0 || k > depth[v]) return -1;
			if (!k) return v;
			if (k == depth[v]) return order[0];
			return shape_ == 2 ? parent[v] : order[in[v] - k];
		}
		if (k < 0) return -1;
		int target = nodes[v].position + nodes[v].offset - k;
		if (target < 0) return -1;
		while (nodes[v].head + nodes[v].offset > target) v = nodes[v].parent;
		return order[target - nodes[v].offset];
	}
	int jump(int u, int v, int k) const {
		check(u), check(v);
		if (k < 0) return -1;
		if (!k) return u;
		if (shape_ == 1) {
			if (head[u] == head[v]) {
				int delta = in[v] - in[u];
				if (k > (delta < 0 ? -delta : delta)) return -1;
				return order[in[u] + (delta < 0 ? -k : k)];
			}
			int a = depth[u], b = depth[v];
			if (k > a + b) return -1;
			if (k == a) return order[0];
			return k < a ? order[in[u] - k] : order[in[v] - (a + b - k)];
		}
		if (shape_ == 2) {
			int d = (u != center_) + (v != center_);
			if (u == v || k > d) return -1;
			return k == d ? v : center_;
		}
		int from = u, to = v, target = nodes[u].position + nodes[u].offset - k;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) {
				if (nodes[u].head + nodes[u].offset <= target) return order[target - nodes[u].offset];
				u = nodes[u].parent;
			} else v = nodes[v].parent;
		}
		int w = nodes[u].position < nodes[v].position ? u : v;
		int d = nodes[w].position + nodes[w].offset;
		int length = nodes[from].position + nodes[from].offset + nodes[to].position + nodes[to].offset - 2 * d;
		if (k > length) return -1;
		if (target >= d) return order[target - nodes[u].offset];
		return ancestor(to, length - k);
	}
	std::pair<int, int> subtree(int v, bool edge = false) const {
		check(v);
		return {in[v] + edge, out[v]};
	}
	int edge_vertex(int id) const {
		assert(0 <= id && id < int(edges.size()));
		auto [u, v] = edges[id];
		check(u);
		return parent[u] == v ? u : v;
	}
	template <class F>
	void for_each_path(int u, int v, F &&f, bool edge = false) const {
		check(u), check(v);
		if (shape_ == 1) {
			int x = in[u], y = in[v];
			if (head[u] == head[v]) {
				int l = std::min(x, y) + edge, r = std::max(x, y) + 1;
				if (l < r) f(l, r, x > y);
			} else if (head[u] == order[0]) {
				if (edge < x + 1) f(int(edge), x + 1, true);
				f(in[head[v]], y + 1, false);
			} else {
				f(in[head[u]], x + 1, true);
				if (edge < y + 1) f(int(edge), y + 1, false);
			}
			return;
		}
		std::array<std::array<int, 2>, 32> right;
		int count = 0;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) {
				f(nodes[u].head, nodes[u].position + 1, true);
				u = nodes[u].parent;
			} else {
				assert(count < int(right.size()));
				right[count++] = {nodes[v].head, nodes[v].position + 1};
				v = nodes[v].parent;
			}
		}
		bool reversed = nodes[u].position > nodes[v].position;
		int l = std::min(nodes[u].position, nodes[v].position) + edge, r = std::max(nodes[u].position, nodes[v].position) + 1;
		if (l < r) f(l, r, reversed);
		while (count) {
			auto [a, b] = right[--count];
			f(a, b, false);
		}
	}
	std::vector<Segment> path(int u, int v, bool edge = false) const {
		std::vector<Segment> result;
		for_each_path(u, v, [&](int l, int r, bool reversed) { result.push_back({l, r, reversed}); }, edge);
		return result;
	}
};

#line 11 "components/static_top_tree_structure.hpp"

namespace static_top_tree_detail {
struct Structure {
	enum Kind : unsigned char { Vertex, Compress, Rake };
	struct Node {
		int parent = -1, left = -1, right = -1, index = -1;
		Kind kind = Vertex;
	};
	std::vector<Node> nodes;
	std::vector<int> order, parent, edge_child;
	int root = -1, root_vertex = -1, paths = 0, points = 0, height = 0;
	Structure() = default;
	explicit Structure(const HLD& tree) { build(tree); }
	void build(const HLD& tree) {
		int n = tree.n;
		assert(n <= std::numeric_limits<int>::max() / 2);
		assert(int(tree.order.size()) == n);
		nodes.assign(n, {}), order.clear();
		nodes.reserve(std::max(0, 2 * n - 1)), order.reserve(std::max(0, 2 * n - 1));
		parent = tree.parent;
		edge_child.clear(), edge_child.reserve(tree.edges.size());
		for (auto [u, v] : tree.edges) edge_child.push_back(parent[u] == v ? u : v);
		paths = n, points = 0, root = -1, height = 0;
		root_vertex = n ? tree.order[0] : -1;
		for (int v = 0; v < n; ++v) nodes[v].index = v;
		std::vector<std::pair<int, int>> heads(n), stack, heap;
		auto join = [&](std::pair<int, int> a, std::pair<int, int> b, Kind kind) {
			int id = int(nodes.size());
			nodes.push_back({-1, a.second, b.second, kind == Compress ? paths++ : points++, kind});
			nodes[a.second].parent = nodes[b.second].parent = id;
			order.push_back(id);
			return std::pair<int, int>{std::max(a.first, b.first) + 1, id};
		};
		auto merge = [&] {
			auto b = stack.back(); stack.pop_back();
			auto a = stack.back(); stack.back() = join(a, b, Compress);
		};
		for (int i = n - 1; i >= 0; --i) {
			int head = tree.order[i];
			if (tree.head[head] != head) continue;
			stack.clear();
			for (int v = head; v != -1; v = tree.heavy[v]) {
				heap.clear();
				for (int j = tree.in[v] + 1; j < tree.out[v];) {
					int u = tree.order[j];
					if (u != tree.heavy[v]) heap.push_back(heads[u]);
					j = tree.out[u];
				}
				using Greater = std::greater<std::pair<int, int>>;
				std::make_heap(heap.begin(), heap.end(), Greater{});
				while (heap.size() > 1) {
					std::pop_heap(heap.begin(), heap.end(), Greater{});
					auto a = heap.back(); heap.pop_back();
					std::pop_heap(heap.begin(), heap.end(), Greater{});
					auto b = heap.back(); heap.back() = join(a, b, Rake);
					std::push_heap(heap.begin(), heap.end(), Greater{});
				}
				int h = 0;
				if (!heap.empty()) {
					nodes[v].left = heap[0].second;
					nodes[heap[0].second].parent = v;
					h = heap[0].first + 1;
				}
				order.push_back(v);
				stack.emplace_back(h, v);
				while (true) {
					int s = int(stack.size());
					if (s >= 3 && (stack[s - 3].first == stack[s - 2].first || stack[s - 3].first <= stack[s - 1].first)) {
						auto last = stack.back(); stack.pop_back();
						merge(), stack.push_back(last);
					} else if (s >= 2 && stack[s - 2].first <= stack[s - 1].first) merge();
					else break;
				}
			}
			while (stack.size() > 1) merge();
			heads[head] = stack[0];
			root = stack[0].second, height = stack[0].first;
		}
	}
};
}

#line 8 "tree/static_top_tree.hpp"

template <class DP>
class StaticTopTree {
	using Structure = static_top_tree_detail::Structure;
	using PathValue = typename DP::Path;
	using PointValue = typename DP::Point;
	struct Link { int index = -1; Structure::Kind kind = Structure::Vertex; bool right = false; };
	struct VertexNode { typename DP::Vertex info; PointValue light; Link up; };
	struct PathNode { PathValue child[2]; Link up; };
	struct PointNode { PointValue child[2]; Link up; };
	std::vector<VertexNode> vertices_;
	std::vector<PathNode> paths_;
	std::vector<PointNode> points_;
	std::vector<int> parent_, edge_child_;
	PathValue all_ = DP::path_identity();
	int root_ = -1;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < size()); }

public:
	using Vertex = typename DP::Vertex;
	using Path = typename DP::Path;
	using Point = typename DP::Point;
	StaticTopTree() = default;
	StaticTopTree(const HLD& tree, std::vector<Vertex> values) { build(tree, std::move(values)); }
	void build(const HLD& tree, std::vector<Vertex> values) {
		assert(int(values.size()) == tree.n);
		Structure structure(tree);
		int n = tree.n;
		vertices_.clear(), vertices_.reserve(n);
		for (auto& value : values) vertices_.push_back({std::move(value), DP::point_identity(), {}});
		paths_.assign(structure.paths - n, PathNode{{DP::path_identity(), DP::path_identity()}, {}});
		points_.assign(structure.points, PointNode{{DP::point_identity(), DP::point_identity()}, {}});
		std::vector<Path> paths(structure.paths, DP::path_identity());
		std::vector<Point> points(structure.points, DP::point_identity());
		auto point = [&](int id) {
			if (id == -1) return DP::point_identity();
			const auto& node = structure.nodes[id];
			return node.kind == Structure::Rake ? points[node.index] : DP::add_edge(paths[node.index]);
		};
		for (int id : structure.order) {
			const auto& node = structure.nodes[id];
			Link up;
			if (node.parent != -1) {
				const auto& p = structure.nodes[node.parent];
				up = {p.kind == Structure::Compress ? p.index - n : p.index, p.kind, p.right == id};
			}
			if (node.kind == Structure::Vertex) {
				auto& v = vertices_[id];
				v.light = point(node.left), v.up = up;
				paths[id] = DP::add_vertex(v.light, v.info);
			} else if (node.kind == Structure::Compress) {
				auto& v = paths_[node.index - n];
				v = {{paths[structure.nodes[node.left].index], paths[structure.nodes[node.right].index]}, up};
				paths[node.index] = DP::compress(v.child[0], v.child[1]);
			} else {
				auto& v = points_[node.index];
				v = {{point(node.left), point(node.right)}, up};
				points[node.index] = DP::rake(v.child[0], v.child[1]);
			}
		}
		all_ = n ? paths[structure.nodes[structure.root].index] : DP::path_identity();
		root_ = structure.root_vertex;
		parent_ = std::move(structure.parent), edge_child_ = std::move(structure.edge_child);
	}
	int size() const { return int(vertices_.size()); }
	bool empty() const { return vertices_.empty(); }
	int root() const { return root_; }
	int parent(int v) const { check(v); return parent_[v]; }
	int edge_vertex(int e) const {
		assert(0 <= e && e < int(edge_child_.size()));
		return edge_child_[e];
	}
	const Vertex& get(int v) const { check(v); return vertices_[v].info; }
	void set(int v, const Vertex& value) {
		check(v);
		auto& vertex = vertices_[v];
		vertex.info = value;
		Path path = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1) {
			while (up.index != -1 && up.kind == Structure::Compress) {
				auto& node = paths_[up.index];
				node.child[up.right] = path;
				path = DP::compress(node.child[0], node.child[1]), up = node.up;
			}
			if (up.index == -1) break;
			Point point = DP::add_edge(path);
			while (up.kind == Structure::Rake) {
				auto& node = points_[up.index];
				node.child[up.right] = point;
				point = DP::rake(node.child[0], node.child[1]), up = node.up;
			}
			auto& node = vertices_[up.index];
			node.light = point;
			path = DP::add_vertex(point, node.info), up = node.up;
		}
		all_ = path;
	}
	Path all_prod() const { return all_; }
	Point dp() const { return DP::add_edge(all_); }
	Path subtree_prod(int v) const {
		check(v);
		const auto& vertex = vertices_[v];
		Path result = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1 && up.kind == Structure::Compress) {
			const auto& node = paths_[up.index];
			if (!up.right) result = DP::compress(result, node.child[1]);
			up = node.up;
		}
		return result;
	}
	Path prod(int v) const {
		check(v);
		Point light = vertices_[v].light;
		Path result = DP::path_identity();
		Link up = vertices_[v].up;
		while (true) {
			Path above = DP::path_identity(), below = DP::path_identity();
			while (up.index != -1 && up.kind == Structure::Compress) {
				const auto& node = paths_[up.index];
				if (!up.right) below = DP::compress(below, node.child[1]);
				else above = DP::compress(node.child[0], above);
				up = node.up;
			}
			light = DP::rake(light, DP::add_edge(below));
			result = DP::compress(above, DP::compress(DP::add_vertex(light, vertices_[v].info), result));
			if (up.index == -1) return result;
			light = DP::point_identity();
			while (up.kind == Structure::Rake) {
				const auto& node = points_[up.index];
				if (!up.right) light = DP::rake(light, node.child[1]);
				else light = DP::rake(node.child[0], light);
				up = node.up;
			}
			v = up.index, up = vertices_[v].up;
		}
	}
};

#ifndef STATIC_TOP_TREE_HPP
#define STATIC_TOP_TREE_HPP

#include <cassert>
#include <utility>
#include <vector>
#include "../components/static_top_tree_structure.hpp"

template <class DP>
class StaticTopTree {
	using Structure = static_top_tree_detail::Structure;
	using PathValue = typename DP::Path;
	using PointValue = typename DP::Point;
	struct Link { int index = -1; Structure::Kind kind = Structure::Vertex; bool right = false; };
	struct VertexNode { typename DP::Vertex info; PointValue light; Link up; };
	struct PathNode { PathValue child[2]; Link up; };
	struct PointNode { PointValue child[2]; Link up; };
	std::vector<VertexNode> vertices_;
	std::vector<PathNode> paths_;
	std::vector<PointNode> points_;
	std::vector<int> parent_, edge_child_;
	PathValue all_ = DP::path_identity();
	int root_ = -1;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < size()); }

  public:
	using Vertex = typename DP::Vertex;
	using Path = typename DP::Path;
	using Point = typename DP::Point;
	StaticTopTree() = default;
	StaticTopTree(const HLD& tree, std::vector<Vertex> values) { build(tree, std::move(values)); }
	void build(const HLD& tree, std::vector<Vertex> values) {
		assert(int(values.size()) == tree.n);
		Structure structure(tree);
		int n = tree.n;
		vertices_.clear(), vertices_.reserve(n);
		for (auto& value : values) vertices_.push_back({std::move(value), DP::point_identity(), {}});
		paths_.assign(structure.paths - n, PathNode{{DP::path_identity(), DP::path_identity()}, {}});
		points_.assign(structure.points, PointNode{{DP::point_identity(), DP::point_identity()}, {}});
		std::vector<Path> paths(structure.paths, DP::path_identity());
		std::vector<Point> points(structure.points, DP::point_identity());
		auto point = [&](int id) {
			if (id == -1) return DP::point_identity();
			const auto& node = structure.nodes[id];
			return node.kind == Structure::Rake ? points[node.index] : DP::add_edge(paths[node.index]);
		};
		for (int id : structure.order) {
			const auto& node = structure.nodes[id];
			Link up;
			if (node.parent != -1) {
				const auto& p = structure.nodes[node.parent];
				up = {p.kind == Structure::Compress ? p.index - n : p.index, p.kind, p.right == id};
			}
			if (node.kind == Structure::Vertex) {
				auto& v = vertices_[id];
				v.light = point(node.left), v.up = up;
				paths[id] = DP::add_vertex(v.light, v.info);
			} else if (node.kind == Structure::Compress) {
				auto& v = paths_[node.index - n];
				v = {{paths[structure.nodes[node.left].index], paths[structure.nodes[node.right].index]}, up};
				paths[node.index] = DP::compress(v.child[0], v.child[1]);
			} else {
				auto& v = points_[node.index];
				v = {{point(node.left), point(node.right)}, up};
				points[node.index] = DP::rake(v.child[0], v.child[1]);
			}
		}
		all_ = n ? paths[structure.nodes[structure.root].index] : DP::path_identity();
		root_ = structure.root_vertex;
		parent_ = std::move(structure.parent), edge_child_ = std::move(structure.edge_child);
	}
	int size() const { return int(vertices_.size()); }
	bool empty() const { return vertices_.empty(); }
	int root() const { return root_; }
	int parent(int v) const { check(v); return parent_[v]; }
	int edge_vertex(int e) const {
		assert(0 <= e && e < int(edge_child_.size()));
		return edge_child_[e];
	}
	const Vertex& get(int v) const { check(v); return vertices_[v].info; }
	void set(int v, const Vertex& value) {
		check(v);
		auto& vertex = vertices_[v];
		vertex.info = value;
		Path path = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1) {
			while (up.index != -1 && up.kind == Structure::Compress) {
				auto& node = paths_[up.index];
				node.child[up.right] = path;
				path = DP::compress(node.child[0], node.child[1]), up = node.up;
			}
			if (up.index == -1) break;
			Point point = DP::add_edge(path);
			while (up.kind == Structure::Rake) {
				auto& node = points_[up.index];
				node.child[up.right] = point;
				point = DP::rake(node.child[0], node.child[1]), up = node.up;
			}
			auto& node = vertices_[up.index];
			node.light = point;
			path = DP::add_vertex(point, node.info), up = node.up;
		}
		all_ = path;
	}
	Path all_prod() const { return all_; }
	Point dp() const { return DP::add_edge(all_); }
	Path subtree_prod(int v) const {
		check(v);
		const auto& vertex = vertices_[v];
		Path result = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1 && up.kind == Structure::Compress) {
			const auto& node = paths_[up.index];
			if (!up.right) result = DP::compress(result, node.child[1]);
			up = node.up;
		}
		return result;
	}
	Path prod(int v) const {
		check(v);
		Point light = vertices_[v].light;
		Path result = DP::path_identity();
		Link up = vertices_[v].up;
		while (true) {
			Path above = DP::path_identity(), below = DP::path_identity();
			while (up.index != -1 && up.kind == Structure::Compress) {
				const auto& node = paths_[up.index];
				if (!up.right) below = DP::compress(below, node.child[1]);
				else above = DP::compress(node.child[0], above);
				up = node.up;
			}
			light = DP::rake(light, DP::add_edge(below));
			result = DP::compress(above, DP::compress(DP::add_vertex(light, vertices_[v].info), result));
			if (up.index == -1) return result;
			light = DP::point_identity();
			while (up.kind == Structure::Rake) {
				const auto& node = points_[up.index];
				if (!up.right) light = DP::rake(light, node.child[1]);
				else light = DP::rake(node.child[0], light);
				up = node.up;
			}
			v = up.index, up = vertices_[v].up;
		}
	}
};

#endif

#line 1 "tree/static_top_tree.hpp"



#include <cassert>
#include <utility>
#include <vector>
#line 1 "components/static_top_tree_structure.hpp"



#include <algorithm>
#line 6 "components/static_top_tree_structure.hpp"
#include <functional>
#include <limits>
#line 1 "tree/hld.hpp"



#line 5 "tree/hld.hpp"
#include <array>
#line 7 "tree/hld.hpp"
#include <cstddef>
#line 11 "tree/hld.hpp"

class HLD {
	int shape_ = 0, center_ = 0;
	struct Node { int position, head, parent, offset; };
	std::vector<Node> nodes;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < n && int(in.size()) == n); }

	void initialize() {
		depth.assign(n, 0);
		size.assign(n, 1);
		heavy.assign(n, -1);
		head.resize(n), in.resize(n), out.resize(n), order.resize(n);
		nodes.resize(n);
		shape_ = center_ = 0;
	}
	void finish(int root) {
		in[root] = 0, out[root] = n, head[root] = root;
		for (int i = n - 2; i >= 0; --i) {
			int v = order[i], p = parent[v];
			depth[v] = depth[p] + 1;
			if (heavy[p] == v) in[v] = in[p] + 1, head[v] = head[p];
			else in[v] = out[p] -= size[v], head[v] = v;
			out[v] = in[v] + size[v];
		}
		for (int v = 0; v < n; ++v) out[v] = in[v] + size[v], order[in[v]] = v;
		parent[root] = -1;
		for (int v = 0; v < n; ++v) nodes[v] = {in[v], in[head[v]], parent[head[v]], depth[v] - in[v]};
	}

  public:
	struct Segment {
		int l, r;
		bool reversed;
	};
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> parent, depth, size, heavy, head, in, out, order;
	explicit HLD(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
		edges.reserve(std::max(0, n - 1));
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		edges.emplace_back(u, v);
		return int(edges.size()) - 1;
	}
	void build(int root = 0) {
		assert(n >= 0 && edges.size() == std::size_t(std::max(0, n - 1)));
		assert(!n || (0 <= root && root < n));
		parent.assign(n, -1);
		initialize();
		if (!n) return;
		std::vector<int> degree(n), neighbors(n);
		for (auto [u, v] : edges) {
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		center_ = int(std::max_element(degree.begin(), degree.end()) - degree.begin());
		shape_ = degree[center_] <= 2 ? 1 : degree[center_] == n - 1 ? 2 : 0;
		degree[root] += 2;
		int count = 0;
		for (int v = 0; v < n; ++v) if (degree[v] == 1) order[count++] = v;
		for (int i = 0; i < count; ++i) {
			int v = order[i], p = neighbors[v];
			parent[v] = p;
			size[p] += size[v];
			if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
			neighbors[p] ^= v;
			if (--degree[p] == 1) order[count++] = p;
		}
		assert(count == n - 1);
		finish(root);
	}
	void build_from_parents(std::vector<int> parents) {
		assert(parents.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		n = static_cast<int>(parents.size());
		parent = std::move(parents);
		initialize();
		edges.clear();
		edges.reserve(std::max(0, n - 1));
		if (!n) return;
		std::fill(out.begin(), out.end(), 0);
		int root = -1;
		bool ordered = true;
		for (int v = 0; v < n; ++v) {
			int p = parent[v];
			assert(-1 <= p && p < n && p != v);
			if (p == -1) {
				assert(root == -1);
				root = v;
			} else {
				++out[p];
				edges.emplace_back(p, v);
				ordered &= p < v;
			}
		}
		assert(root != -1);
		int maximum = 0;
		for (int v = 0; v < n; ++v) {
			int degree = out[v] + (v != root);
			if (degree > maximum) maximum = degree, center_ = v;
		}
		shape_ = maximum <= 2 ? 1 : maximum == n - 1 ? 2 : 0;
		if (ordered) {
			for (int v = n - 1; v > 0; --v) {
				int p = parent[v];
				size[p] += size[v];
				if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
				order[n - 1 - v] = v;
			}
		} else {
			int count = 0;
			for (int v = 0; v < n; ++v) if (!out[v] && v != root) order[count++] = v;
			for (int i = 0; i < count; ++i) {
				int v = order[i], p = parent[v];
				size[p] += size[v];
				if (heavy[p] == -1 || size[heavy[p]] < size[v]) heavy[p] = v;
				if (!--out[p] && p != root) order[count++] = p;
			}
			assert(count == n - 1);
		}
		finish(root);
	}
	int lca(int u, int v) const {
		check(u), check(v);
		if (shape_ == 1) return head[u] != head[v] ? order[0] : in[u] < in[v] ? u : v;
		if (shape_ == 2) return u == v ? u : u == order[0] || v == order[0] ? order[0] : center_;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) u = nodes[u].parent;
			else v = nodes[v].parent;
		}
		return nodes[u].position < nodes[v].position ? u : v;
	}
	int dist(int u, int v) const {
		int w = lca(u, v);
		return depth[u] + depth[v] - 2 * depth[w];
	}
	bool is_ancestor(int u, int v) const {
		check(u), check(v);
		return in[u] <= in[v] && in[v] < out[u];
	}
	int ancestor(int v, int k) const {
		check(v);
		if (shape_) {
			if (k < 0 || k > depth[v]) return -1;
			if (!k) return v;
			if (k == depth[v]) return order[0];
			return shape_ == 2 ? parent[v] : order[in[v] - k];
		}
		if (k < 0) return -1;
		int target = nodes[v].position + nodes[v].offset - k;
		if (target < 0) return -1;
		while (nodes[v].head + nodes[v].offset > target) v = nodes[v].parent;
		return order[target - nodes[v].offset];
	}
	int jump(int u, int v, int k) const {
		check(u), check(v);
		if (k < 0) return -1;
		if (!k) return u;
		if (shape_ == 1) {
			if (head[u] == head[v]) {
				int delta = in[v] - in[u];
				if (k > (delta < 0 ? -delta : delta)) return -1;
				return order[in[u] + (delta < 0 ? -k : k)];
			}
			int a = depth[u], b = depth[v];
			if (k > a + b) return -1;
			if (k == a) return order[0];
			return k < a ? order[in[u] - k] : order[in[v] - (a + b - k)];
		}
		if (shape_ == 2) {
			int d = (u != center_) + (v != center_);
			if (u == v || k > d) return -1;
			return k == d ? v : center_;
		}
		int from = u, to = v, target = nodes[u].position + nodes[u].offset - k;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) {
				if (nodes[u].head + nodes[u].offset <= target) return order[target - nodes[u].offset];
				u = nodes[u].parent;
			} else v = nodes[v].parent;
		}
		int w = nodes[u].position < nodes[v].position ? u : v;
		int d = nodes[w].position + nodes[w].offset;
		int length = nodes[from].position + nodes[from].offset + nodes[to].position + nodes[to].offset - 2 * d;
		if (k > length) return -1;
		if (target >= d) return order[target - nodes[u].offset];
		return ancestor(to, length - k);
	}
	std::pair<int, int> subtree(int v, bool edge = false) const {
		check(v);
		return {in[v] + edge, out[v]};
	}
	int edge_vertex(int id) const {
		assert(0 <= id && id < int(edges.size()));
		auto [u, v] = edges[id];
		check(u);
		return parent[u] == v ? u : v;
	}
	template <class F>
	void for_each_path(int u, int v, F &&f, bool edge = false) const {
		check(u), check(v);
		if (shape_ == 1) {
			int x = in[u], y = in[v];
			if (head[u] == head[v]) {
				int l = std::min(x, y) + edge, r = std::max(x, y) + 1;
				if (l < r) f(l, r, x > y);
			} else if (head[u] == order[0]) {
				if (edge < x + 1) f(int(edge), x + 1, true);
				f(in[head[v]], y + 1, false);
			} else {
				f(in[head[u]], x + 1, true);
				if (edge < y + 1) f(int(edge), y + 1, false);
			}
			return;
		}
		std::array<std::array<int, 2>, 32> right;
		int count = 0;
		while (nodes[u].head != nodes[v].head) {
			if (nodes[u].position > nodes[v].position) {
				f(nodes[u].head, nodes[u].position + 1, true);
				u = nodes[u].parent;
			} else {
				assert(count < int(right.size()));
				right[count++] = {nodes[v].head, nodes[v].position + 1};
				v = nodes[v].parent;
			}
		}
		bool reversed = nodes[u].position > nodes[v].position;
		int l = std::min(nodes[u].position, nodes[v].position) + edge, r = std::max(nodes[u].position, nodes[v].position) + 1;
		if (l < r) f(l, r, reversed);
		while (count) {
			auto [a, b] = right[--count];
			f(a, b, false);
		}
	}
	std::vector<Segment> path(int u, int v, bool edge = false) const {
		std::vector<Segment> result;
		for_each_path(u, v, [&](int l, int r, bool reversed) { result.push_back({l, r, reversed}); }, edge);
		return result;
	}
};


#line 11 "components/static_top_tree_structure.hpp"

namespace static_top_tree_detail {
struct Structure {
	enum Kind : unsigned char { Vertex, Compress, Rake };
	struct Node {
		int parent = -1, left = -1, right = -1, index = -1;
		Kind kind = Vertex;
	};
	std::vector<Node> nodes;
	std::vector<int> order, parent, edge_child;
	int root = -1, root_vertex = -1, paths = 0, points = 0, height = 0;
	Structure() = default;
	explicit Structure(const HLD& tree) { build(tree); }
	void build(const HLD& tree) {
		int n = tree.n;
		assert(n <= std::numeric_limits<int>::max() / 2);
		assert(int(tree.order.size()) == n);
		nodes.assign(n, {}), order.clear();
		nodes.reserve(std::max(0, 2 * n - 1)), order.reserve(std::max(0, 2 * n - 1));
		parent = tree.parent;
		edge_child.clear(), edge_child.reserve(tree.edges.size());
		for (auto [u, v] : tree.edges) edge_child.push_back(parent[u] == v ? u : v);
		paths = n, points = 0, root = -1, height = 0;
		root_vertex = n ? tree.order[0] : -1;
		for (int v = 0; v < n; ++v) nodes[v].index = v;
		std::vector<std::pair<int, int>> heads(n), stack, heap;
		auto join = [&](std::pair<int, int> a, std::pair<int, int> b, Kind kind) {
			int id = int(nodes.size());
			nodes.push_back({-1, a.second, b.second, kind == Compress ? paths++ : points++, kind});
			nodes[a.second].parent = nodes[b.second].parent = id;
			order.push_back(id);
			return std::pair<int, int>{std::max(a.first, b.first) + 1, id};
		};
		auto merge = [&] {
			auto b = stack.back(); stack.pop_back();
			auto a = stack.back(); stack.back() = join(a, b, Compress);
		};
		for (int i = n - 1; i >= 0; --i) {
			int head = tree.order[i];
			if (tree.head[head] != head) continue;
			stack.clear();
			for (int v = head; v != -1; v = tree.heavy[v]) {
				heap.clear();
				for (int j = tree.in[v] + 1; j < tree.out[v];) {
					int u = tree.order[j];
					if (u != tree.heavy[v]) heap.push_back(heads[u]);
					j = tree.out[u];
				}
				using Greater = std::greater<std::pair<int, int>>;
				std::make_heap(heap.begin(), heap.end(), Greater{});
				while (heap.size() > 1) {
					std::pop_heap(heap.begin(), heap.end(), Greater{});
					auto a = heap.back(); heap.pop_back();
					std::pop_heap(heap.begin(), heap.end(), Greater{});
					auto b = heap.back(); heap.back() = join(a, b, Rake);
					std::push_heap(heap.begin(), heap.end(), Greater{});
				}
				int h = 0;
				if (!heap.empty()) {
					nodes[v].left = heap[0].second;
					nodes[heap[0].second].parent = v;
					h = heap[0].first + 1;
				}
				order.push_back(v);
				stack.emplace_back(h, v);
				while (true) {
					int s = int(stack.size());
					if (s >= 3 && (stack[s - 3].first == stack[s - 2].first || stack[s - 3].first <= stack[s - 1].first)) {
						auto last = stack.back(); stack.pop_back();
						merge(), stack.push_back(last);
					} else if (s >= 2 && stack[s - 2].first <= stack[s - 1].first) merge();
					else break;
				}
			}
			while (stack.size() > 1) merge();
			heads[head] = stack[0];
			root = stack[0].second, height = stack[0].first;
		}
	}
};
}


#line 8 "tree/static_top_tree.hpp"

template <class DP>
class StaticTopTree {
	using Structure = static_top_tree_detail::Structure;
	using PathValue = typename DP::Path;
	using PointValue = typename DP::Point;
	struct Link { int index = -1; Structure::Kind kind = Structure::Vertex; bool right = false; };
	struct VertexNode { typename DP::Vertex info; PointValue light; Link up; };
	struct PathNode { PathValue child[2]; Link up; };
	struct PointNode { PointValue child[2]; Link up; };
	std::vector<VertexNode> vertices_;
	std::vector<PathNode> paths_;
	std::vector<PointNode> points_;
	std::vector<int> parent_, edge_child_;
	PathValue all_ = DP::path_identity();
	int root_ = -1;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < size()); }

  public:
	using Vertex = typename DP::Vertex;
	using Path = typename DP::Path;
	using Point = typename DP::Point;
	StaticTopTree() = default;
	StaticTopTree(const HLD& tree, std::vector<Vertex> values) { build(tree, std::move(values)); }
	void build(const HLD& tree, std::vector<Vertex> values) {
		assert(int(values.size()) == tree.n);
		Structure structure(tree);
		int n = tree.n;
		vertices_.clear(), vertices_.reserve(n);
		for (auto& value : values) vertices_.push_back({std::move(value), DP::point_identity(), {}});
		paths_.assign(structure.paths - n, PathNode{{DP::path_identity(), DP::path_identity()}, {}});
		points_.assign(structure.points, PointNode{{DP::point_identity(), DP::point_identity()}, {}});
		std::vector<Path> paths(structure.paths, DP::path_identity());
		std::vector<Point> points(structure.points, DP::point_identity());
		auto point = [&](int id) {
			if (id == -1) return DP::point_identity();
			const auto& node = structure.nodes[id];
			return node.kind == Structure::Rake ? points[node.index] : DP::add_edge(paths[node.index]);
		};
		for (int id : structure.order) {
			const auto& node = structure.nodes[id];
			Link up;
			if (node.parent != -1) {
				const auto& p = structure.nodes[node.parent];
				up = {p.kind == Structure::Compress ? p.index - n : p.index, p.kind, p.right == id};
			}
			if (node.kind == Structure::Vertex) {
				auto& v = vertices_[id];
				v.light = point(node.left), v.up = up;
				paths[id] = DP::add_vertex(v.light, v.info);
			} else if (node.kind == Structure::Compress) {
				auto& v = paths_[node.index - n];
				v = {{paths[structure.nodes[node.left].index], paths[structure.nodes[node.right].index]}, up};
				paths[node.index] = DP::compress(v.child[0], v.child[1]);
			} else {
				auto& v = points_[node.index];
				v = {{point(node.left), point(node.right)}, up};
				points[node.index] = DP::rake(v.child[0], v.child[1]);
			}
		}
		all_ = n ? paths[structure.nodes[structure.root].index] : DP::path_identity();
		root_ = structure.root_vertex;
		parent_ = std::move(structure.parent), edge_child_ = std::move(structure.edge_child);
	}
	int size() const { return int(vertices_.size()); }
	bool empty() const { return vertices_.empty(); }
	int root() const { return root_; }
	int parent(int v) const { check(v); return parent_[v]; }
	int edge_vertex(int e) const {
		assert(0 <= e && e < int(edge_child_.size()));
		return edge_child_[e];
	}
	const Vertex& get(int v) const { check(v); return vertices_[v].info; }
	void set(int v, const Vertex& value) {
		check(v);
		auto& vertex = vertices_[v];
		vertex.info = value;
		Path path = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1) {
			while (up.index != -1 && up.kind == Structure::Compress) {
				auto& node = paths_[up.index];
				node.child[up.right] = path;
				path = DP::compress(node.child[0], node.child[1]), up = node.up;
			}
			if (up.index == -1) break;
			Point point = DP::add_edge(path);
			while (up.kind == Structure::Rake) {
				auto& node = points_[up.index];
				node.child[up.right] = point;
				point = DP::rake(node.child[0], node.child[1]), up = node.up;
			}
			auto& node = vertices_[up.index];
			node.light = point;
			path = DP::add_vertex(point, node.info), up = node.up;
		}
		all_ = path;
	}
	Path all_prod() const { return all_; }
	Point dp() const { return DP::add_edge(all_); }
	Path subtree_prod(int v) const {
		check(v);
		const auto& vertex = vertices_[v];
		Path result = DP::add_vertex(vertex.light, vertex.info);
		Link up = vertex.up;
		while (up.index != -1 && up.kind == Structure::Compress) {
			const auto& node = paths_[up.index];
			if (!up.right) result = DP::compress(result, node.child[1]);
			up = node.up;
		}
		return result;
	}
	Path prod(int v) const {
		check(v);
		Point light = vertices_[v].light;
		Path result = DP::path_identity();
		Link up = vertices_[v].up;
		while (true) {
			Path above = DP::path_identity(), below = DP::path_identity();
			while (up.index != -1 && up.kind == Structure::Compress) {
				const auto& node = paths_[up.index];
				if (!up.right) below = DP::compress(below, node.child[1]);
				else above = DP::compress(node.child[0], above);
				up = node.up;
			}
			light = DP::rake(light, DP::add_edge(below));
			result = DP::compress(above, DP::compress(DP::add_vertex(light, vertices_[v].info), result));
			if (up.index == -1) return result;
			light = DP::point_identity();
			while (up.kind == Structure::Rake) {
				const auto& node = points_[up.index];
				if (!up.right) light = DP::rake(light, node.child[1]);
				else light = DP::rake(node.child[0], light);
				up = node.up;
			}
			v = up.index, up = vertices_[v].up;
		}
	}
};