最小シュタイナー木

graph/steiner_tree.hpp · GitHub で見る

共通ページ

非負重みの無向グラフで、指定した端点を全て連結にする最小コストの木を求めます。指定していない頂点も利用できます。厳密解を求めるため、端点数が小さい場合に使います。

#include "lib/graph/steiner_tree.hpp"
#include <cassert>

int main() {
	SteinerTree<> graph(4);
	graph.add_edge(0, 3, 2);
	graph.add_edge(1, 3, 3);
	graph.add_edge(2, 3, 4);
	graph.add_edge(0, 1, 10);
	auto result = graph.solve({0, 1, 2});
	assert(result && result->cost == 9);
	assert(result->edges.size() == 3);
	for (int id : result->edges) {
		auto [u, v, cost] = graph.get_edge(id);
	}
	assert(graph.minimum_cost({0, 2}) == 6);
}

操作・メンバー	内容・返り値
`SteinerTree<Cost,Sum>(n = 0)`	頂点数を指定。既定値は `Cost=int64_t`、`Sum=Cost`
`add_edge(u,v,cost)`	非負重みの無向辺を追加し、0 始まりの辺 ID（`int`）を返す
`solve(terminals,inf = numeric_limits<Sum>::max())`	`optional<Result>`。指定端点を全て含む最小シュタイナー木
`minimum_cost(terminals,inf = numeric_limits<Sum>::max())`	`optional<Sum>`。採用辺が不要な場合の最小コスト
`result.cost`	採用辺の重みの総和（`Sum`）
`result.edges`	採用した辺 ID の `vector<int>`。順序は未規定
`get_edge(id)`	入力した辺を `Edge{from,to,cost}` として取得
`edges()`	入力順の辺一覧を `const vector<Edge>&` で取得
`size()` / `edge_count()`	頂点数／辺数を `int` で取得
`reserve(m)`	辺 `m` 本分の領域を予約
`clear()`	全辺を削除。頂点数は維持し、辺 ID は 0 から再開

頂点番号は [0,n)、辺 ID は [0,edge_count()) です。terminals は頂点番号の vector<int> を渡します。順序は任意で、重複は取り除きます。異なる端点が0個または1個なら、コスト0・辺なしを返します。空グラフも扱えます。

多重辺・自己ループ・重み0の辺に対応し、採用辺には閉路を含めません。全端点が連結にできない場合は nullopt です。端点を含まない別の連結成分があっても構いません。solve と minimum_cost は入力を変更せず、辺の追加後にも再実行できます。返された結果はグラフを参照しません。

Cost は辺重み、Sum は経路・木の総和の型です。どちらも整数型、またはどちらも浮動小数点型とし、非負の Cost の全ての値を Sum で表現できるようにします。例えば SteinerTree<uint32_t,uint64_t>、SteinerTree<int64_t,__int128_t> が使えます。重みは有限の非負値とし、浮動小数点では通常の丸め誤差があります。

inf は正数で、求めたい答えより厳密に大きい値を指定します。コストが inf 以上の解は扱わず、答えがその範囲にしかない場合も nullopt を返します。整数の加算は上限を確認して行います。型の最大値と等しい答えが必要なら、より広い Sum を指定してください。

頂点数は INT_MAX 未満、辺数は INT_MAX/2 以下とします。異なる端点数は31以下とし、DP の領域がメモリに収まる必要があります。端点数は指数的な時間・空間に影響するため、実用上はさらに小さい入力に使います。

入力された端点数を \(t\)、重複を除いた端点数を \(k\)、頂点数を \(n\)、辺数を \(m\) とします。solve・minimum_cost は、64 bit 以下の整数の Sum では \(O(t\log t+3^k n+2^k(n+m)w)\) 時間（\(w\) は Sum のビット数）、その他の型では \(O(t\log t+3^k n+2^k(n+m)\log(n+m))\) 時間です。空間は \(O(t+2^k n+m)\) です。コストだけが必要なら、採用辺の復元領域を使わない minimum_cost を選べます。

構築は \(O(1)\)、add_edge は償却 \(O(1)\)、reserve(m) は \(O(m)\)、clear は \(O(m)\)、辺・サイズの参照は \(O(1)\) です。型の演算・比較を \(O(1)\) とします。

依存ライブラリ

検証コード

test/steiner_tree.test.cpp

コード

#line 1 "graph/steiner_tree.hpp"

#line 1 "components/dijkstra_queue.hpp"

#line 1 "components/RadixHeap.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Key = std::uint64_t, class T = int>
class RadixHeap {
	static_assert(std::is_integral_v<Key> && !std::is_same_v<Key, bool> && sizeof(Key) <= 8);
	using U = std::make_unsigned_t<Key>;
	using State = std::pair<Key, T>;
	std::vector<State> bucket[std::numeric_limits<U>::digits + 1];
	Key lower;
	std::size_t count = 0;
	int index(Key key) const { return std::bit_width(U(U(key) ^ U(lower))); }
	void refill() {
		assert(count);
		if (!bucket[0].empty()) return;
		int i = 1;
		while (bucket[i].empty()) ++i;
		lower = bucket[i][0].first;
		for (const auto &s : bucket[i]) lower = std::min(lower, s.first);
		for (auto &s : bucket[i]) bucket[index(s.first)].push_back(std::move(s));
		bucket[i].clear();
	}

public:
	explicit RadixHeap(Key minimum = 0) : lower(minimum) {}
	RadixHeap(const RadixHeap &) = default;
	RadixHeap &operator=(const RadixHeap &) = default;
	RadixHeap(RadixHeap &&other) noexcept : lower(other.lower), count(std::exchange(other.count, 0)) {
		for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
	}
	RadixHeap &operator=(RadixHeap &&other) noexcept {
		if (this != &other) {
			lower = other.lower;
			count = std::exchange(other.count, 0);
			for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
		}
		return *this;
	}

bool empty() const { return count == 0; }
	std::size_t size() const { return count; }
	Key last() const { return lower; }
	void clear(Key minimum = 0) {
		for (auto &b : bucket) b.clear();
		lower = minimum;
		count = 0;
	}
	void push(State s) {
		assert(s.first >= lower);
		bucket[index(s.first)].push_back(std::move(s));
		++count;
	}
	const State &top() {
		refill();
		return bucket[0].back();
	}
	void pop() {
		refill();
		bucket[0].pop_back();
		--count;
	}
	State pop_value() {
		refill();
		State s = std::move(bucket[0].back());
		bucket[0].pop_back();
		--count;
		return s;
	}
};

#line 10 "components/dijkstra_queue.hpp"
#include <functional>
#line 15 "components/dijkstra_queue.hpp"

namespace shortest_path_detail {
template<class Weight, class Distance>
bool reaches_limit(const Weight &weight, const Distance &limit) {
	if constexpr (std::numeric_limits<Weight>::is_integer && std::numeric_limits<Weight>::is_bounded &&
				  std::numeric_limits<Distance>::is_integer && std::numeric_limits<Distance>::is_bounded) {
		using Compare = std::common_type_t<Weight, Distance>;
		return Compare(weight) >= Compare(limit);
	} else return weight >= limit;
}

template<class T> class RadixQueue {
	static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
	struct State { T key; int vertex; };
	State small_[32];
	std::vector<std::uint64_t> buckets_[33];
	std::uint32_t minimum_[33];
	std::uint32_t occupied_ = 0;
	std::uint64_t last_ = 0;
	std::size_t count_ = 0;
	int mode_ = 0;
	RadixHeap<std::uint64_t> wide_;
	void put(std::uint64_t state) {
		std::uint32_t key = state >> 32;
		int index = std::bit_width(key ^ std::uint32_t(last_));
		buckets_[index].push_back(state);
		if (index) {
			occupied_ |= std::uint32_t(1) << (index - 1);
			minimum_[index] = std::min(minimum_[index], key);
		}
	}
	void promote() {
		if (mode_ == 0) {
			for (std::size_t i = 0; i < count_; ++i) wide_.push({std::uint64_t(small_[i].key), small_[i].vertex});
		} else {
			for (auto &bucket : buckets_) {
				for (auto state : bucket) {
					std::uint64_t key = last_ + std::uint32_t(std::uint32_t(state >> 32) - std::uint32_t(last_));
					wide_.push({key, int(std::uint32_t(state))});
				}
				bucket.clear();
			}
		}
		mode_ = 2;
	}

public:
	bool empty() const { return count_ == 0; }
	void push(T key, int vertex) {
		assert(key >= 0 && std::uint64_t(key) >= last_);
		if (mode_ == 0 && count_ < 32) {
			small_[count_++] = {key, vertex};
			return;
		}
		if (mode_ == 0) {
			bool narrow = std::uint64_t(key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			for (std::size_t i = 0; i < count_; ++i)
				narrow &= std::uint64_t(small_[i].key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			if (narrow) {
				std::fill_n(minimum_, 33, std::numeric_limits<std::uint32_t>::max());
				for (std::size_t i = 0; i < count_; ++i)
					put((std::uint64_t(std::uint32_t(small_[i].key)) << 32) | std::uint32_t(small_[i].vertex));
				mode_ = 1;
			} else promote();
		}
		if (mode_ == 1 && std::uint64_t(key) - last_ > std::uint64_t(std::numeric_limits<std::int32_t>::max())) promote();
		if (mode_ == 2) wide_.push({std::uint64_t(key), vertex});
		else put((std::uint64_t(std::uint32_t(key)) << 32) | std::uint32_t(vertex));
		++count_;
	}
	std::pair<T, int> pop() {
		assert(count_);
		if (mode_ == 0) {
			std::size_t best = 0;
			for (std::size_t i = 1; i < count_; ++i)
				if (small_[i].key < small_[best].key) best = i;
			State state = small_[best];
			small_[best] = small_[--count_];
			last_ = std::uint64_t(state.key);
			return {state.key, state.vertex};
		}
		if (mode_ == 2) {
			auto state = wide_.pop_value();
			last_ = state.first;
			--count_;
			return {T(state.first), state.second};
		}
		if (buckets_[0].empty()) {
			int index = std::countr_zero(occupied_) + 1;
			last_ += std::uint32_t(minimum_[index] - std::uint32_t(last_));
			minimum_[index] = std::numeric_limits<std::uint32_t>::max();
			occupied_ &= occupied_ - 1;
			if (buckets_[index].size() == 1) {
				auto state = buckets_[index].back();
				buckets_[index].clear();
				--count_;
				return {T(last_), int(std::uint32_t(state))};
			}
			for (auto state : buckets_[index]) put(state);
			buckets_[index].clear();
		}
		auto state = buckets_[0].back();
		buckets_[0].pop_back();
		--count_;
		return {T(last_), int(std::uint32_t(state))};
	}
};

template<class T> class BinaryQueue {
	using State = std::pair<T, int>;
	std::vector<State> heap_;

public:
	bool empty() const { return heap_.empty(); }
	void push(T cost, int vertex) {
		heap_.emplace_back(std::move(cost), vertex);
		std::push_heap(heap_.begin(), heap_.end(), std::greater<State>());
	}
	State pop() {
		std::pop_heap(heap_.begin(), heap_.end(), std::greater<State>());
		State state = std::move(heap_.back());
		heap_.pop_back();
		return state;
	}
};

template<class T>
using DistanceQueue = std::conditional_t<std::is_integral_v<T> && sizeof(T) <= 8, RadixQueue<T>, BinaryQueue<T>>;
}

#line 1 "components/undirected_csr.hpp"

#line 7 "components/undirected_csr.hpp"
#include <memory>
#include <span>
#line 12 "components/undirected_csr.hpp"

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

#line 1 "data_structure/union_find.hpp"

#line 7 "data_structure/union_find.hpp"

class UnionFind {
	std::vector<int> parent_;
	int count_ = 0;

public:
	explicit UnionFind(int n = 0) : count_(n) {
		assert(n >= 0);
		parent_.assign(n, -1);
	}
	[[nodiscard]] int size() const { return static_cast<int>(parent_.size()); }
	[[nodiscard]] int count() const { return count_; }
	[[nodiscard]] int leader(int v) {
		assert(0 <= v && v < size());
		while (parent_[v] >= 0) {
			int p = parent_[v];
			if (parent_[p] < 0) return p;
			v = parent_[v] = parent_[p];
		}
		return v;
	}
	int merge(int a, int b) {
		a = leader(a), b = leader(b);
		if (a == b) return a;
		if (parent_[a] > parent_[b]) std::swap(a, b);
		parent_[a] += parent_[b];
		parent_[b] = a;
		--count_;
		return a;
	}
	[[nodiscard]] bool same(int a, int b) { return leader(a) == leader(b); }
	[[nodiscard]] int size(int v) { return -parent_[leader(v)]; }
	[[nodiscard]] std::vector<std::vector<int>> groups() {
		std::vector<int> index(size(), -1);
		std::vector<std::vector<int>> result(count_);
		int next = 0;
		for (int v = 0; v < size(); ++v) if (parent_[v] < 0) {
			index[v] = next;
			result[next++].reserve(-parent_[v]);
		}
		for (int v = 0; v < size(); ++v) result[index[leader(v)]].push_back(v);
		return result;
	}
};

#line 13 "graph/steiner_tree.hpp"
#include <optional>
#include <stdexcept>
#line 18 "graph/steiner_tree.hpp"

template<class Cost = std::int64_t, class Sum = Cost>
class SteinerTree {
	static_assert((std::numeric_limits<Cost>::is_integer || std::is_floating_point_v<Cost>) && !std::is_same_v<Cost, bool>);
	static_assert((std::numeric_limits<Sum>::is_integer || std::is_floating_point_v<Sum>) && !std::is_same_v<Sum, bool>);
	static_assert(std::numeric_limits<Cost>::is_integer == std::numeric_limits<Sum>::is_integer);
	static_assert(std::numeric_limits<Cost>::digits <= std::numeric_limits<Sum>::digits);
	int n_;

public:
	struct Edge { int from, to; Cost cost; };
	struct Result { Sum cost = 0; std::vector<int> edges; };

private:
	std::vector<Edge> edges_;
	template<bool Restore>
	std::optional<Result> run(std::vector<int> terminals, Sum inf) const {
		assert(inf > 0);
		for ([[maybe_unused]] int v : terminals) assert(0 <= v && v < n_);
		std::sort(terminals.begin(), terminals.end());
		terminals.erase(std::unique(terminals.begin(), terminals.end()), terminals.end());
		if (terminals.size() <= 1) return Result{};
		int root = terminals.back();
		terminals.pop_back();
		auto graph = [&] {
			std::vector<std::pair<int, int>> endpoints;
			endpoints.reserve(edges_.size());
			for (const auto &e : edges_) endpoints.emplace_back(e.from, e.to);
			return UndirectedCSR(n_, endpoints);
		}();
		{
			std::vector<unsigned char> seen(n_);
			std::vector<int> work{root};
			seen[root] = 1;
			for (std::size_t i = 0; i < work.size(); ++i)
				for (auto [u, id] : graph[work[i]]) if (!seen[u] && Sum(edges_[id].cost) < inf) {
					seen[u] = 1, work.push_back(u);
				}
			for (int v : terminals) if (!seen[v]) return std::nullopt;
		}
		if (terminals.size() >= std::numeric_limits<int>::digits) throw std::length_error("SteinerTree terminals");
		int states = int(1U << terminals.size());
		if (std::size_t(states) > std::vector<Sum>().max_size() / std::size_t(n_)) throw std::length_error("SteinerTree states");
		std::size_t count = std::size_t(states) * n_;
		std::vector<Sum> dp(count, inf);
		std::vector<int> trace;
		if constexpr (Restore) trace.assign(count, -1);
		bool dense = std::uint64_t(n_) * n_ <= 4 * std::uint64_t(edges_.size());
		std::vector<unsigned char> used(dense ? n_ : 0);
		for (int mask = 1; mask < states; ++mask) {
			std::size_t offset = std::size_t(mask) * n_;
			Sum *current = dp.data() + offset;
			if (std::has_single_bit(unsigned(mask))) current[terminals[std::countr_zero(unsigned(mask))]] = 0;
			else for (int part = (mask - 1) & mask; part > (mask ^ part); part = (part - 1) & mask) {
				const Sum *left = dp.data() + std::size_t(part) * n_;
				const Sum *right = dp.data() + std::size_t(mask ^ part) * n_;
				for (int v = 0; v < n_; ++v) {
					if (right[v] >= inf - left[v]) continue;
					Sum next = left[v] + right[v];
					if (next < current[v]) {
						current[v] = next;
						if constexpr (Restore) trace[offset + v] = -part - 1;
					}
				}
			}
			auto relax = [&](int v, Sum cost, auto push) {
				for (auto [u, id] : graph[v]) {
					Sum weight = Sum(edges_[id].cost);
					if (weight >= inf - cost) continue;
					Sum next = cost + weight;
					if (next < current[u]) {
						current[u] = next;
						if constexpr (Restore) trace[offset + u] = id;
						push(next, u);
					}
				}
			};
			if (dense) {
				std::fill(used.begin(), used.end(), 0);
				for (int iteration = 0; iteration < n_; ++iteration) {
					int v = -1;
					Sum cost = inf;
					for (int u = 0; u < n_; ++u) if (!used[u] && current[u] < cost) cost = current[u], v = u;
					if (v < 0 || (mask == states - 1 && cost >= current[root])) break;
					used[v] = 1;
					relax(v, cost, [](Sum, int) {});
				}
			} else {
				shortest_path_detail::DistanceQueue<Sum> queue;
				for (int v = 0; v < n_; ++v) if (current[v] < inf) queue.push(current[v], v);
				while (!queue.empty()) {
					auto [cost, v] = queue.pop();
					if (cost != current[v]) continue;
					if (mask == states - 1 && cost >= current[root]) break;
					relax(v, cost, [&](Sum next, int u) { queue.push(next, u); });
				}
			}
		}
		Sum answer = dp[std::size_t(states - 1) * n_ + root];
		if (!(answer < inf)) return std::nullopt;
		Result result;
		result.cost = answer;
		if constexpr (Restore) {
			UnionFind uf(n_);
			std::vector<std::pair<int, int>> work{ {states - 1, root} };
			while (!work.empty()) {
				auto [mask, v] = work.back();
				work.pop_back();
				while (true) {
					int step = trace[std::size_t(mask) * n_ + v];
					if (step == -1) break;
					if (step < -1) {
						int part = -step - 1;
						work.emplace_back(mask ^ part, v);
						mask = part;
					} else {
						const auto &e = edges_[step];
						if (!uf.same(e.from, e.to)) {
							uf.merge(e.from, e.to);
							result.edges.push_back(step);
						}
						v ^= e.from ^ e.to;
					}
				}
			}
		}
		return result;
	}

public:
	explicit SteinerTree(int n = 0) : n_(n) { assert(0 <= n && n < std::numeric_limits<int>::max()); }
	int size() const { return n_; }
	int edge_count() const { return int(edges_.size()); }
	void reserve(std::size_t m) {
		assert(m <= std::size_t(std::numeric_limits<int>::max() / 2));
		edges_.reserve(m);
	}
	int add_edge(int u, int v, Cost cost) {
		assert(0 <= u && u < n_ && 0 <= v && v < n_ && cost >= 0);
		assert(edges_.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		int id = edge_count();
		edges_.push_back({u, v, cost});
		return id;
	}
	Edge get_edge(int id) const { assert(0 <= id && id < edge_count()); return edges_[id]; }
	const std::vector<Edge> &edges() const { return edges_; }
	void clear() { edges_.clear(); }
	std::optional<Result> solve(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		return run<true>(std::move(terminals), inf);
	}
	std::optional<Sum> minimum_cost(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		auto result = run<false>(std::move(terminals), inf);
		if (!result) return std::nullopt;
		return result->cost;
	}
};

#ifndef STEINER_TREE_HPP
#define STEINER_TREE_HPP

#include "../components/dijkstra_queue.hpp"
#include "../components/undirected_csr.hpp"
#include "../data_structure/union_find.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

template<class Cost = std::int64_t, class Sum = Cost>
class SteinerTree {
	static_assert((std::numeric_limits<Cost>::is_integer || std::is_floating_point_v<Cost>) && !std::is_same_v<Cost, bool>);
	static_assert((std::numeric_limits<Sum>::is_integer || std::is_floating_point_v<Sum>) && !std::is_same_v<Sum, bool>);
	static_assert(std::numeric_limits<Cost>::is_integer == std::numeric_limits<Sum>::is_integer);
	static_assert(std::numeric_limits<Cost>::digits <= std::numeric_limits<Sum>::digits);
	int n_;

  public:
	struct Edge { int from, to; Cost cost; };
	struct Result { Sum cost = 0; std::vector<int> edges; };

  private:
	std::vector<Edge> edges_;
	template<bool Restore>
	std::optional<Result> run(std::vector<int> terminals, Sum inf) const {
		assert(inf > 0);
		for ([[maybe_unused]] int v : terminals) assert(0 <= v && v < n_);
		std::sort(terminals.begin(), terminals.end());
		terminals.erase(std::unique(terminals.begin(), terminals.end()), terminals.end());
		if (terminals.size() <= 1) return Result{};
		int root = terminals.back();
		terminals.pop_back();
		auto graph = [&] {
			std::vector<std::pair<int, int>> endpoints;
			endpoints.reserve(edges_.size());
			for (const auto &e : edges_) endpoints.emplace_back(e.from, e.to);
			return UndirectedCSR(n_, endpoints);
		}();
		{
			std::vector<unsigned char> seen(n_);
			std::vector<int> work{root};
			seen[root] = 1;
			for (std::size_t i = 0; i < work.size(); ++i)
				for (auto [u, id] : graph[work[i]]) if (!seen[u] && Sum(edges_[id].cost) < inf) {
					seen[u] = 1, work.push_back(u);
				}
			for (int v : terminals) if (!seen[v]) return std::nullopt;
		}
		if (terminals.size() >= std::numeric_limits<int>::digits) throw std::length_error("SteinerTree terminals");
		int states = int(1U << terminals.size());
		if (std::size_t(states) > std::vector<Sum>().max_size() / std::size_t(n_)) throw std::length_error("SteinerTree states");
		std::size_t count = std::size_t(states) * n_;
		std::vector<Sum> dp(count, inf);
		std::vector<int> trace;
		if constexpr (Restore) trace.assign(count, -1);
		bool dense = std::uint64_t(n_) * n_ <= 4 * std::uint64_t(edges_.size());
		std::vector<unsigned char> used(dense ? n_ : 0);
		for (int mask = 1; mask < states; ++mask) {
			std::size_t offset = std::size_t(mask) * n_;
			Sum *current = dp.data() + offset;
			if (std::has_single_bit(unsigned(mask))) current[terminals[std::countr_zero(unsigned(mask))]] = 0;
			else for (int part = (mask - 1) & mask; part > (mask ^ part); part = (part - 1) & mask) {
				const Sum *left = dp.data() + std::size_t(part) * n_;
				const Sum *right = dp.data() + std::size_t(mask ^ part) * n_;
				for (int v = 0; v < n_; ++v) {
					if (right[v] >= inf - left[v]) continue;
					Sum next = left[v] + right[v];
					if (next < current[v]) {
						current[v] = next;
						if constexpr (Restore) trace[offset + v] = -part - 1;
					}
				}
			}
			auto relax = [&](int v, Sum cost, auto push) {
				for (auto [u, id] : graph[v]) {
					Sum weight = Sum(edges_[id].cost);
					if (weight >= inf - cost) continue;
					Sum next = cost + weight;
					if (next < current[u]) {
						current[u] = next;
						if constexpr (Restore) trace[offset + u] = id;
						push(next, u);
					}
				}
			};
			if (dense) {
				std::fill(used.begin(), used.end(), 0);
				for (int iteration = 0; iteration < n_; ++iteration) {
					int v = -1;
					Sum cost = inf;
					for (int u = 0; u < n_; ++u) if (!used[u] && current[u] < cost) cost = current[u], v = u;
					if (v < 0 || (mask == states - 1 && cost >= current[root])) break;
					used[v] = 1;
					relax(v, cost, [](Sum, int) {});
				}
			} else {
				shortest_path_detail::DistanceQueue<Sum> queue;
				for (int v = 0; v < n_; ++v) if (current[v] < inf) queue.push(current[v], v);
				while (!queue.empty()) {
					auto [cost, v] = queue.pop();
					if (cost != current[v]) continue;
					if (mask == states - 1 && cost >= current[root]) break;
					relax(v, cost, [&](Sum next, int u) { queue.push(next, u); });
				}
			}
		}
		Sum answer = dp[std::size_t(states - 1) * n_ + root];
		if (!(answer < inf)) return std::nullopt;
		Result result;
		result.cost = answer;
		if constexpr (Restore) {
			UnionFind uf(n_);
			std::vector<std::pair<int, int>> work{ {states - 1, root} };
			while (!work.empty()) {
				auto [mask, v] = work.back();
				work.pop_back();
				while (true) {
					int step = trace[std::size_t(mask) * n_ + v];
					if (step == -1) break;
					if (step < -1) {
						int part = -step - 1;
						work.emplace_back(mask ^ part, v);
						mask = part;
					} else {
						const auto &e = edges_[step];
						if (!uf.same(e.from, e.to)) {
							uf.merge(e.from, e.to);
							result.edges.push_back(step);
						}
						v ^= e.from ^ e.to;
					}
				}
			}
		}
		return result;
	}

  public:
	explicit SteinerTree(int n = 0) : n_(n) { assert(0 <= n && n < std::numeric_limits<int>::max()); }
	int size() const { return n_; }
	int edge_count() const { return int(edges_.size()); }
	void reserve(std::size_t m) {
		assert(m <= std::size_t(std::numeric_limits<int>::max() / 2));
		edges_.reserve(m);
	}
	int add_edge(int u, int v, Cost cost) {
		assert(0 <= u && u < n_ && 0 <= v && v < n_ && cost >= 0);
		assert(edges_.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		int id = edge_count();
		edges_.push_back({u, v, cost});
		return id;
	}
	Edge get_edge(int id) const { assert(0 <= id && id < edge_count()); return edges_[id]; }
	const std::vector<Edge> &edges() const { return edges_; }
	void clear() { edges_.clear(); }
	std::optional<Result> solve(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		return run<true>(std::move(terminals), inf);
	}
	std::optional<Sum> minimum_cost(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		auto result = run<false>(std::move(terminals), inf);
		if (!result) return std::nullopt;
		return result->cost;
	}
};

#endif

#line 1 "graph/steiner_tree.hpp"



#line 1 "components/dijkstra_queue.hpp"



#line 1 "components/RadixHeap.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Key = std::uint64_t, class T = int>
class RadixHeap {
	static_assert(std::is_integral_v<Key> && !std::is_same_v<Key, bool> && sizeof(Key) <= 8);
	using U = std::make_unsigned_t<Key>;
	using State = std::pair<Key, T>;
	std::vector<State> bucket[std::numeric_limits<U>::digits + 1];
	Key lower;
	std::size_t count = 0;
	int index(Key key) const { return std::bit_width(U(U(key) ^ U(lower))); }
	void refill() {
		assert(count);
		if (!bucket[0].empty()) return;
		int i = 1;
		while (bucket[i].empty()) ++i;
		lower = bucket[i][0].first;
		for (const auto &s : bucket[i]) lower = std::min(lower, s.first);
		for (auto &s : bucket[i]) bucket[index(s.first)].push_back(std::move(s));
		bucket[i].clear();
	}

  public:
	explicit RadixHeap(Key minimum = 0) : lower(minimum) {}
	RadixHeap(const RadixHeap &) = default;
	RadixHeap &operator=(const RadixHeap &) = default;
	RadixHeap(RadixHeap &&other) noexcept : lower(other.lower), count(std::exchange(other.count, 0)) {
		for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
	}
	RadixHeap &operator=(RadixHeap &&other) noexcept {
		if (this != &other) {
			lower = other.lower;
			count = std::exchange(other.count, 0);
			for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
		}
		return *this;
	}

	bool empty() const { return count == 0; }
	std::size_t size() const { return count; }
	Key last() const { return lower; }
	void clear(Key minimum = 0) {
		for (auto &b : bucket) b.clear();
		lower = minimum;
		count = 0;
	}
	void push(State s) {
		assert(s.first >= lower);
		bucket[index(s.first)].push_back(std::move(s));
		++count;
	}
	const State &top() {
		refill();
		return bucket[0].back();
	}
	void pop() {
		refill();
		bucket[0].pop_back();
		--count;
	}
	State pop_value() {
		refill();
		State s = std::move(bucket[0].back());
		bucket[0].pop_back();
		--count;
		return s;
	}
};


#line 10 "components/dijkstra_queue.hpp"
#include <functional>
#line 15 "components/dijkstra_queue.hpp"

namespace shortest_path_detail {
template<class Weight, class Distance>
bool reaches_limit(const Weight &weight, const Distance &limit) {
	if constexpr (std::numeric_limits<Weight>::is_integer && std::numeric_limits<Weight>::is_bounded &&
				  std::numeric_limits<Distance>::is_integer && std::numeric_limits<Distance>::is_bounded) {
		using Compare = std::common_type_t<Weight, Distance>;
		return Compare(weight) >= Compare(limit);
	} else return weight >= limit;
}

template<class T> class RadixQueue {
	static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
	struct State { T key; int vertex; };
	State small_[32];
	std::vector<std::uint64_t> buckets_[33];
	std::uint32_t minimum_[33];
	std::uint32_t occupied_ = 0;
	std::uint64_t last_ = 0;
	std::size_t count_ = 0;
	int mode_ = 0;
	RadixHeap<std::uint64_t> wide_;
	void put(std::uint64_t state) {
		std::uint32_t key = state >> 32;
		int index = std::bit_width(key ^ std::uint32_t(last_));
		buckets_[index].push_back(state);
		if (index) {
			occupied_ |= std::uint32_t(1) << (index - 1);
			minimum_[index] = std::min(minimum_[index], key);
		}
	}
	void promote() {
		if (mode_ == 0) {
			for (std::size_t i = 0; i < count_; ++i) wide_.push({std::uint64_t(small_[i].key), small_[i].vertex});
		} else {
			for (auto &bucket : buckets_) {
				for (auto state : bucket) {
					std::uint64_t key = last_ + std::uint32_t(std::uint32_t(state >> 32) - std::uint32_t(last_));
					wide_.push({key, int(std::uint32_t(state))});
				}
				bucket.clear();
			}
		}
		mode_ = 2;
	}

  public:
	bool empty() const { return count_ == 0; }
	void push(T key, int vertex) {
		assert(key >= 0 && std::uint64_t(key) >= last_);
		if (mode_ == 0 && count_ < 32) {
			small_[count_++] = {key, vertex};
			return;
		}
		if (mode_ == 0) {
			bool narrow = std::uint64_t(key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			for (std::size_t i = 0; i < count_; ++i)
				narrow &= std::uint64_t(small_[i].key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			if (narrow) {
				std::fill_n(minimum_, 33, std::numeric_limits<std::uint32_t>::max());
				for (std::size_t i = 0; i < count_; ++i)
					put((std::uint64_t(std::uint32_t(small_[i].key)) << 32) | std::uint32_t(small_[i].vertex));
				mode_ = 1;
			} else promote();
		}
		if (mode_ == 1 && std::uint64_t(key) - last_ > std::uint64_t(std::numeric_limits<std::int32_t>::max())) promote();
		if (mode_ == 2) wide_.push({std::uint64_t(key), vertex});
		else put((std::uint64_t(std::uint32_t(key)) << 32) | std::uint32_t(vertex));
		++count_;
	}
	std::pair<T, int> pop() {
		assert(count_);
		if (mode_ == 0) {
			std::size_t best = 0;
			for (std::size_t i = 1; i < count_; ++i)
				if (small_[i].key < small_[best].key) best = i;
			State state = small_[best];
			small_[best] = small_[--count_];
			last_ = std::uint64_t(state.key);
			return {state.key, state.vertex};
		}
		if (mode_ == 2) {
			auto state = wide_.pop_value();
			last_ = state.first;
			--count_;
			return {T(state.first), state.second};
		}
		if (buckets_[0].empty()) {
			int index = std::countr_zero(occupied_) + 1;
			last_ += std::uint32_t(minimum_[index] - std::uint32_t(last_));
			minimum_[index] = std::numeric_limits<std::uint32_t>::max();
			occupied_ &= occupied_ - 1;
			if (buckets_[index].size() == 1) {
				auto state = buckets_[index].back();
				buckets_[index].clear();
				--count_;
				return {T(last_), int(std::uint32_t(state))};
			}
			for (auto state : buckets_[index]) put(state);
			buckets_[index].clear();
		}
		auto state = buckets_[0].back();
		buckets_[0].pop_back();
		--count_;
		return {T(last_), int(std::uint32_t(state))};
	}
};

template<class T> class BinaryQueue {
	using State = std::pair<T, int>;
	std::vector<State> heap_;

  public:
	bool empty() const { return heap_.empty(); }
	void push(T cost, int vertex) {
		heap_.emplace_back(std::move(cost), vertex);
		std::push_heap(heap_.begin(), heap_.end(), std::greater<State>());
	}
	State pop() {
		std::pop_heap(heap_.begin(), heap_.end(), std::greater<State>());
		State state = std::move(heap_.back());
		heap_.pop_back();
		return state;
	}
};

template<class T>
using DistanceQueue = std::conditional_t<std::is_integral_v<T> && sizeof(T) <= 8, RadixQueue<T>, BinaryQueue<T>>;
}


#line 1 "components/undirected_csr.hpp"



#line 7 "components/undirected_csr.hpp"
#include <memory>
#include <span>
#line 12 "components/undirected_csr.hpp"

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};


#line 1 "data_structure/union_find.hpp"



#line 7 "data_structure/union_find.hpp"

class UnionFind {
	std::vector<int> parent_;
	int count_ = 0;

  public:
	explicit UnionFind(int n = 0) : count_(n) {
		assert(n >= 0);
		parent_.assign(n, -1);
	}
	[[nodiscard]] int size() const { return static_cast<int>(parent_.size()); }
	[[nodiscard]] int count() const { return count_; }
	[[nodiscard]] int leader(int v) {
		assert(0 <= v && v < size());
		while (parent_[v] >= 0) {
			int p = parent_[v];
			if (parent_[p] < 0) return p;
			v = parent_[v] = parent_[p];
		}
		return v;
	}
	int merge(int a, int b) {
		a = leader(a), b = leader(b);
		if (a == b) return a;
		if (parent_[a] > parent_[b]) std::swap(a, b);
		parent_[a] += parent_[b];
		parent_[b] = a;
		--count_;
		return a;
	}
	[[nodiscard]] bool same(int a, int b) { return leader(a) == leader(b); }
	[[nodiscard]] int size(int v) { return -parent_[leader(v)]; }
	[[nodiscard]] std::vector<std::vector<int>> groups() {
		std::vector<int> index(size(), -1);
		std::vector<std::vector<int>> result(count_);
		int next = 0;
		for (int v = 0; v < size(); ++v) if (parent_[v] < 0) {
			index[v] = next;
			result[next++].reserve(-parent_[v]);
		}
		for (int v = 0; v < size(); ++v) result[index[leader(v)]].push_back(v);
		return result;
	}
};


#line 13 "graph/steiner_tree.hpp"
#include <optional>
#include <stdexcept>
#line 18 "graph/steiner_tree.hpp"

template<class Cost = std::int64_t, class Sum = Cost>
class SteinerTree {
	static_assert((std::numeric_limits<Cost>::is_integer || std::is_floating_point_v<Cost>) && !std::is_same_v<Cost, bool>);
	static_assert((std::numeric_limits<Sum>::is_integer || std::is_floating_point_v<Sum>) && !std::is_same_v<Sum, bool>);
	static_assert(std::numeric_limits<Cost>::is_integer == std::numeric_limits<Sum>::is_integer);
	static_assert(std::numeric_limits<Cost>::digits <= std::numeric_limits<Sum>::digits);
	int n_;

  public:
	struct Edge { int from, to; Cost cost; };
	struct Result { Sum cost = 0; std::vector<int> edges; };

  private:
	std::vector<Edge> edges_;
	template<bool Restore>
	std::optional<Result> run(std::vector<int> terminals, Sum inf) const {
		assert(inf > 0);
		for ([[maybe_unused]] int v : terminals) assert(0 <= v && v < n_);
		std::sort(terminals.begin(), terminals.end());
		terminals.erase(std::unique(terminals.begin(), terminals.end()), terminals.end());
		if (terminals.size() <= 1) return Result{};
		int root = terminals.back();
		terminals.pop_back();
		auto graph = [&] {
			std::vector<std::pair<int, int>> endpoints;
			endpoints.reserve(edges_.size());
			for (const auto &e : edges_) endpoints.emplace_back(e.from, e.to);
			return UndirectedCSR(n_, endpoints);
		}();
		{
			std::vector<unsigned char> seen(n_);
			std::vector<int> work{root};
			seen[root] = 1;
			for (std::size_t i = 0; i < work.size(); ++i)
				for (auto [u, id] : graph[work[i]]) if (!seen[u] && Sum(edges_[id].cost) < inf) {
					seen[u] = 1, work.push_back(u);
				}
			for (int v : terminals) if (!seen[v]) return std::nullopt;
		}
		if (terminals.size() >= std::numeric_limits<int>::digits) throw std::length_error("SteinerTree terminals");
		int states = int(1U << terminals.size());
		if (std::size_t(states) > std::vector<Sum>().max_size() / std::size_t(n_)) throw std::length_error("SteinerTree states");
		std::size_t count = std::size_t(states) * n_;
		std::vector<Sum> dp(count, inf);
		std::vector<int> trace;
		if constexpr (Restore) trace.assign(count, -1);
		bool dense = std::uint64_t(n_) * n_ <= 4 * std::uint64_t(edges_.size());
		std::vector<unsigned char> used(dense ? n_ : 0);
		for (int mask = 1; mask < states; ++mask) {
			std::size_t offset = std::size_t(mask) * n_;
			Sum *current = dp.data() + offset;
			if (std::has_single_bit(unsigned(mask))) current[terminals[std::countr_zero(unsigned(mask))]] = 0;
			else for (int part = (mask - 1) & mask; part > (mask ^ part); part = (part - 1) & mask) {
				const Sum *left = dp.data() + std::size_t(part) * n_;
				const Sum *right = dp.data() + std::size_t(mask ^ part) * n_;
				for (int v = 0; v < n_; ++v) {
					if (right[v] >= inf - left[v]) continue;
					Sum next = left[v] + right[v];
					if (next < current[v]) {
						current[v] = next;
						if constexpr (Restore) trace[offset + v] = -part - 1;
					}
				}
			}
			auto relax = [&](int v, Sum cost, auto push) {
				for (auto [u, id] : graph[v]) {
					Sum weight = Sum(edges_[id].cost);
					if (weight >= inf - cost) continue;
					Sum next = cost + weight;
					if (next < current[u]) {
						current[u] = next;
						if constexpr (Restore) trace[offset + u] = id;
						push(next, u);
					}
				}
			};
			if (dense) {
				std::fill(used.begin(), used.end(), 0);
				for (int iteration = 0; iteration < n_; ++iteration) {
					int v = -1;
					Sum cost = inf;
					for (int u = 0; u < n_; ++u) if (!used[u] && current[u] < cost) cost = current[u], v = u;
					if (v < 0 || (mask == states - 1 && cost >= current[root])) break;
					used[v] = 1;
					relax(v, cost, [](Sum, int) {});
				}
			} else {
				shortest_path_detail::DistanceQueue<Sum> queue;
				for (int v = 0; v < n_; ++v) if (current[v] < inf) queue.push(current[v], v);
				while (!queue.empty()) {
					auto [cost, v] = queue.pop();
					if (cost != current[v]) continue;
					if (mask == states - 1 && cost >= current[root]) break;
					relax(v, cost, [&](Sum next, int u) { queue.push(next, u); });
				}
			}
		}
		Sum answer = dp[std::size_t(states - 1) * n_ + root];
		if (!(answer < inf)) return std::nullopt;
		Result result;
		result.cost = answer;
		if constexpr (Restore) {
			UnionFind uf(n_);
			std::vector<std::pair<int, int>> work{ {states - 1, root} };
			while (!work.empty()) {
				auto [mask, v] = work.back();
				work.pop_back();
				while (true) {
					int step = trace[std::size_t(mask) * n_ + v];
					if (step == -1) break;
					if (step < -1) {
						int part = -step - 1;
						work.emplace_back(mask ^ part, v);
						mask = part;
					} else {
						const auto &e = edges_[step];
						if (!uf.same(e.from, e.to)) {
							uf.merge(e.from, e.to);
							result.edges.push_back(step);
						}
						v ^= e.from ^ e.to;
					}
				}
			}
		}
		return result;
	}

  public:
	explicit SteinerTree(int n = 0) : n_(n) { assert(0 <= n && n < std::numeric_limits<int>::max()); }
	int size() const { return n_; }
	int edge_count() const { return int(edges_.size()); }
	void reserve(std::size_t m) {
		assert(m <= std::size_t(std::numeric_limits<int>::max() / 2));
		edges_.reserve(m);
	}
	int add_edge(int u, int v, Cost cost) {
		assert(0 <= u && u < n_ && 0 <= v && v < n_ && cost >= 0);
		assert(edges_.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		int id = edge_count();
		edges_.push_back({u, v, cost});
		return id;
	}
	Edge get_edge(int id) const { assert(0 <= id && id < edge_count()); return edges_[id]; }
	const std::vector<Edge> &edges() const { return edges_; }
	void clear() { edges_.clear(); }
	std::optional<Result> solve(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		return run<true>(std::move(terminals), inf);
	}
	std::optional<Sum> minimum_cost(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
		auto result = run<false>(std::move(terminals), inf);
		if (!result) return std::nullopt;
		return result->cost;
	}
};