special_spanning_trees.hpp¶
求非负双权之和乘积最小的生成树，以及二维整数点的切比雪夫最小生成树；前者用带剪枝的支撑点搜索，后者变换坐标后复用曼哈顿 MST。
Complexity: Time: \(O(m + Q (n + M \log (M + 1)))\) product tree, \(Q\) MST queries and \(M\) non-loop edges; \(O(n \log (n + 1))\) Chebyshev MST. Space: \(O(n + m + Q)\) product tree, \(O(n)\) Chebyshev MST.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(m+Q(n+M log(M+1))) product tree, Q MST queries and M non-loop edges;
/// O(n log(n+1)) Chebyshev MST. Space: O(n+m+Q) product tree, O(n) Chebyshev MST.
#include "noya/graph/manhattan_mst.hpp"
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
struct bicriteria_spanning_tree_result {
std::int64_t s1 = 0;
std::int64_t s2 = 0;
std::vector<int> eid;
};
/// @brief Minimize (sum wa)*(sum wb) on a connected undirected graph.
/// Non-loop weights must be nonnegative. Loops are ignored; parallel edges
/// keep their original IDs. Require n>=1, valid endpoints, at most INT_MAX
/// edges, and both component sums of every queried MST representable by int64.
/// Supported-point search uses Q input-dependent MST queries, not a fixed
/// number of rounds. Preserve original scalarized-cost/edge-ID tie decisions.
inline bicriteria_spanning_tree_result minimum_product_spanning_tree(
int n,
const std::vector<std::tuple<std::int64_t, std::int64_t, int, int>> &es) {
assert(n >= 1 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
struct record { __int128 key; int id; };
std::vector<record> order;
for (int id = 0; id < int(es.size()); ++id) {
const auto &[wa, wb, u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
assert(wa >= 0 && wb >= 0);
order.push_back({0, id});
}
if (n == 1) return {};
using point = std::pair<std::int64_t, std::int64_t>;
auto product = [](point p) { return __int128(p.first) * p.second; };
auto less = [](const record &a, const record &b) {
return a.key != b.key ? a.key < b.key : a.id < b.id;
};
bicriteria_spanning_tree_result current;
current.eid.reserve(n - 1);
auto tree = [&](std::int64_t ca, std::int64_t cb) -> point {
for (auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
item.key = __int128(ca) * a + __int128(cb) * b;
}
if (!std::is_sorted(order.begin(), order.end(), less))
std::sort(order.begin(), order.end(), less);
atcoder::dsu dsu(n);
current.eid.clear();
__int128 a_sum = 0, b_sum = 0;
for (const auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
int x = dsu.leader(u), y = dsu.leader(v);
if (x == y) continue;
dsu.merge(x, y);
a_sum += a; b_sum += b;
current.eid.push_back(item.id);
if (int(current.eid.size()) == n - 1) break;
}
assert(int(current.eid.size()) == n - 1);
assert(a_sum <= std::numeric_limits<std::int64_t>::max());
assert(b_sum <= std::numeric_limits<std::int64_t>::max());
current.s1 = std::int64_t(a_sum); current.s2 = std::int64_t(b_sum);
return {current.s1, current.s2};
};
auto x = tree(1, 0);
auto best = current;
auto y = tree(0, 1);
if (product(y) <= product(x)) best = current;
// Recursion retains only two-coordinate points; the query buffers are shared.
auto search = [&](auto &self, point l, point r) -> void {
// This hull interval lies in [l.first,r.first] x [r.second,l.second].
if (__int128(l.first) * r.second >= product({best.s1, best.s2})) return;
std::int64_t ca = l.second - r.second, cb = r.first - l.first;
auto mid = tree(ca, cb);
__int128 bound = __int128(ca) * l.first + __int128(cb) * l.second;
__int128 value = __int128(ca) * mid.first + __int128(cb) * mid.second;
if (value >= bound) return;
if (product(mid) < product({best.s1, best.s2})) best = current;
self(self, l, mid);
self(self, mid, r);
};
search(search, x, y);
return best;
}
/// @brief Chebyshev-distance MST of integer points in O(n log(n+1)) time.
/// Return (int64 total, original point-index pairs). Empty/single inputs cost 0;
/// duplicate points are allowed, input is unchanged, and tied optimum trees
/// may differ from complete-graph Kruskal. Endpoints in each pair are increasing.
/// Coordinates may span int64; the resulting total must fit int64.
inline std::pair<std::int64_t, std::vector<std::pair<int, int>>>
chebyshev_mst(const std::vector<std::pair<std::int64_t, std::int64_t>> &pt) {
assert(pt.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(pt.size());
if (n <= 1) return {0, {}};
std::vector<__int128> x, y;
x.reserve(n); y.reserve(n);
for (auto [a, b] : pt) {
x.push_back(__int128(a) + b);
y.push_back(__int128(a) - b);
}
// |dx+dy|+|dx-dy| = 2*max(|dx|,|dy|); transformed distances are even.
auto edges = manhattan_edges(std::move(x), std::move(y));
atcoder::dsu dsu(n);
__int128 cost = 0;
std::vector<std::pair<int, int>> result;
result.reserve(n - 1);
for (auto [distance, a, b] : edges) {
int u = dsu.leader(a), v = dsu.leader(b);
if (u == v) continue;
dsu.merge(u, v);
assert(distance % 2 == 0);
cost += distance / 2;
if (a > b) std::swap(a, b);
result.emplace_back(a, b);
if (int(result.size()) == n - 1) break;
}
assert(int(result.size()) == n - 1);
assert(cost <= std::numeric_limits<std::int64_t>::max());
return {std::int64_t(cost), std::move(result)};
}
} // namespace noya
// NOYA_SPECIAL_SPANNING_TREES_HPP
#ifndef NOYA_SPECIAL_SPANNING_TREES_HPP
#define NOYA_SPECIAL_SPANNING_TREES_HPP 1
/// @complexity Time: O(m+Q(n+M log(M+1))) product tree, Q MST queries and M non-loop edges;
/// O(n log(n+1)) Chebyshev MST. Space: O(n+m+Q) product tree, O(n) Chebyshev MST.
#include "noya/graph/manhattan_mst.hpp"
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
struct bicriteria_spanning_tree_result {
std::int64_t s1 = 0;
std::int64_t s2 = 0;
std::vector<int> eid;
};
/// @brief Minimize (sum wa)*(sum wb) on a connected undirected graph.
/// Non-loop weights must be nonnegative. Loops are ignored; parallel edges
/// keep their original IDs. Require n>=1, valid endpoints, at most INT_MAX
/// edges, and both component sums of every queried MST representable by int64.
/// Supported-point search uses Q input-dependent MST queries, not a fixed
/// number of rounds. Preserve original scalarized-cost/edge-ID tie decisions.
inline bicriteria_spanning_tree_result minimum_product_spanning_tree(
int n,
const std::vector<std::tuple<std::int64_t, std::int64_t, int, int>> &es) {
assert(n >= 1 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
struct record { __int128 key; int id; };
std::vector<record> order;
for (int id = 0; id < int(es.size()); ++id) {
const auto &[wa, wb, u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
assert(wa >= 0 && wb >= 0);
order.push_back({0, id});
}
if (n == 1) return {};
using point = std::pair<std::int64_t, std::int64_t>;
auto product = [](point p) { return __int128(p.first) * p.second; };
auto less = [](const record &a, const record &b) {
return a.key != b.key ? a.key < b.key : a.id < b.id;
};
bicriteria_spanning_tree_result current;
current.eid.reserve(n - 1);
auto tree = [&](std::int64_t ca, std::int64_t cb) -> point {
for (auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
item.key = __int128(ca) * a + __int128(cb) * b;
}
if (!std::is_sorted(order.begin(), order.end(), less))
std::sort(order.begin(), order.end(), less);
atcoder::dsu dsu(n);
current.eid.clear();
__int128 a_sum = 0, b_sum = 0;
for (const auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
int x = dsu.leader(u), y = dsu.leader(v);
if (x == y) continue;
dsu.merge(x, y);
a_sum += a; b_sum += b;
current.eid.push_back(item.id);
if (int(current.eid.size()) == n - 1) break;
}
assert(int(current.eid.size()) == n - 1);
assert(a_sum <= std::numeric_limits<std::int64_t>::max());
assert(b_sum <= std::numeric_limits<std::int64_t>::max());
current.s1 = std::int64_t(a_sum); current.s2 = std::int64_t(b_sum);
return {current.s1, current.s2};
};
auto x = tree(1, 0);
auto best = current;
auto y = tree(0, 1);
if (product(y) <= product(x)) best = current;
// Recursion retains only two-coordinate points; the query buffers are shared.
auto search = [&](auto &self, point l, point r) -> void {
// This hull interval lies in [l.first,r.first] x [r.second,l.second].
if (__int128(l.first) * r.second >= product({best.s1, best.s2})) return;
std::int64_t ca = l.second - r.second, cb = r.first - l.first;
auto mid = tree(ca, cb);
__int128 bound = __int128(ca) * l.first + __int128(cb) * l.second;
__int128 value = __int128(ca) * mid.first + __int128(cb) * mid.second;
if (value >= bound) return;
if (product(mid) < product({best.s1, best.s2})) best = current;
self(self, l, mid);
self(self, mid, r);
};
search(search, x, y);
return best;
}
/// @brief Chebyshev-distance MST of integer points in O(n log(n+1)) time.
/// Return (int64 total, original point-index pairs). Empty/single inputs cost 0;
/// duplicate points are allowed, input is unchanged, and tied optimum trees
/// may differ from complete-graph Kruskal. Endpoints in each pair are increasing.
/// Coordinates may span int64; the resulting total must fit int64.
inline std::pair<std::int64_t, std::vector<std::pair<int, int>>>
chebyshev_mst(const std::vector<std::pair<std::int64_t, std::int64_t>> &pt) {
assert(pt.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(pt.size());
if (n <= 1) return {0, {}};
std::vector<__int128> x, y;
x.reserve(n); y.reserve(n);
for (auto [a, b] : pt) {
x.push_back(__int128(a) + b);
y.push_back(__int128(a) - b);
}
// |dx+dy|+|dx-dy| = 2*max(|dx|,|dy|); transformed distances are even.
auto edges = manhattan_edges(std::move(x), std::move(y));
atcoder::dsu dsu(n);
__int128 cost = 0;
std::vector<std::pair<int, int>> result;
result.reserve(n - 1);
for (auto [distance, a, b] : edges) {
int u = dsu.leader(a), v = dsu.leader(b);
if (u == v) continue;
dsu.merge(u, v);
assert(distance % 2 == 0);
cost += distance / 2;
if (a > b) std::swap(a, b);
result.emplace_back(a, b);
if (int(result.size()) == n - 1) break;
}
assert(int(result.size()) == n - 1);
assert(cost <= std::numeric_limits<std::int64_t>::max());
return {std::int64_t(cost), std::move(result)};
}
} // namespace noya
#endif // NOYA_SPECIAL_SPANNING_TREES_HPP
/// @complexity Time: O(m+Q(n+M log(M+1))) product tree, Q MST queries and M non-loop edges;
/// O(n log(n+1)) Chebyshev MST. Space: O(n+m+Q) product tree, O(n) Chebyshev MST.
// SPDX-License-Identifier: MIT
/*
MIT License
Copyright (c) 2019 Ryotaro Sato
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
/// @complexity Time: O(n log n).
/// Space: O(n).
/// @complexity Time: O(V+E log(E+1)) Kruskal, O(V+E alpha(V+1)) for ordered edges;
/// O(V^2+E) dense Prim. Space: O(V+E) Kruskal; O(V^2+V) dense Prim.
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
return _leader(a);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
int _leader(int a) {
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = _leader(parent_or_size[a]);
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace internal {
inline int64_t spanning_forest_cost(__int128 cost) {
assert(cost >= std::numeric_limits<int64_t>::min() &&
cost <= std::numeric_limits<int64_t>::max());
return int64_t(cost);
}
template <class T, class Compare>
std::pair<int64_t, std::vector<int>>
kruskal_spanning_forest(int n, const std::vector<T> &es, Compare order) {
assert(n >= 0 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
auto key = [](const T &edge) {
const auto &[w, u, v] = edge;
return std::tuple{w, int(u), int(v)};
};
using Key = decltype(key(es[0]));
struct Record { Key key; int id; };
std::vector<Record> p;
p.reserve(es.size());
for (int i = 0; i < int(es.size()); ++i) {
const auto &[w, u, v] = es[i];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) p.push_back({key(es[i]), i});
}
if (n <= 1 || p.empty()) return {0, {}};
auto cmp = [&](const auto &a, const auto &b) {
return order(std::get<0>(a.key), std::get<0>(b.key));
};
if (!std::is_sorted(p.begin(), p.end(), cmp))
std::sort(p.begin(), p.end(), cmp);
atcoder::dsu dsu(n);
__int128 cost = 0;
std::vector<int> selected;
selected.reserve(std::min(std::size_t(n - 1), p.size()));
for (const auto &[edge, i] : p) {
const auto &[w, u, v] = edge;
int a = dsu.leader(u), b = dsu.leader(v);
if (a == b) continue;
dsu.merge(a, b);
cost += static_cast<__int128>(w);
selected.push_back(i);
if (int(selected.size()) == n - 1) break;
}
return {spanning_forest_cost(cost), std::move(selected)};
}
} // namespace internal
/// @brief Minimum spanning forest by Kruskal. Edges are (weight,u,v).
/// Return (int64 total, original edge IDs), without modifying the input.
/// Integral weights and intermediate sums must fit signed __int128, and the
/// final total must fit int64_t. Loops are ignored; equal optima may differ.
template <class T>
std::pair<int64_t, std::vector<int>>
minimum_spanning_tree(int n, const std::vector<T> &es) {
return internal::kruskal_spanning_forest(n, es, std::less<>{});
}
/// @brief Maximum spanning forest, with the same contract as the minimum.
template <class T>
std::pair<int64_t, std::vector<int>>
maximum_spanning_tree(int n, const std::vector<T> &es) {
return internal::kruskal_spanning_forest(n, es, std::greater<>{});
}
/// @brief Minimum spanning forest by dense Prim; restart in each component.
/// Uses the same edge layout, numeric and ownership contracts as Kruskal.
template <class T>
std::pair<int64_t, std::vector<int>> prim_dense(int n, const std::vector<T> &es) {
assert(n >= 0 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return {0, {}};
std::vector<int> id(std::size_t(n) * n, -1);
int nonloops = 0;
for (int i = 0; i < int(es.size()); ++i) {
const auto &[w, u, v] = es[i];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
++nonloops;
auto &a = id[std::size_t(u) * n + v];
if (a != -1) {
const auto &[old_weight, old_u, old_v] = es[a];
if (!(std::tie(w, u, v) < std::tie(old_weight, old_u, old_v))) continue;
}
a = id[std::size_t(v) * n + u] = i;
}
if (!nonloops) return {0, {}};
std::vector<int> selected, best(n, -1);
selected.reserve(std::min(n - 1, nonloops));
std::vector<unsigned char> used(n);
auto better = [&](int a, int b) {
if (a == -1) return b;
if (b == -1) return a;
const auto &[x, u1, v1] = es[a];
const auto &[y, u2, v2] = es[b];
return x < y ? a : b;
};
__int128 cost = 0;
for (int root = 0; root < n; ++root) if (!used[root]) {
int u = root;
while (true) {
used[u] = true;
int next = -1;
const int *row = id.data() + std::size_t(u) * n;
for (int v = 0; v < n; ++v) if (!used[v]) {
best[v] = better(best[v], row[v]);
next = better(next, best[v]);
}
if (next == -1) break;
selected.push_back(next);
const auto &[w, a, b] = es[next];
cost += static_cast<__int128>(w);
u = used[a] ? b : a;
}
}
return {internal::spanning_forest_cost(cost), std::move(selected)};
}
} // namespace noya
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <map>
#include <numeric>
#include <tuple>
#include <type_traits>
#include <vector>
namespace noya {
/// @brief Compute candidate edges for Manhattan MST in O(n log n).
/// @return Sorted edges as (weight, vertex_i, vertex_j).
/// Integer coordinates up to 64 bits use widened arithmetic. Edge weights
/// must fit T; wider integers and finite floating coordinates must also keep
/// intermediate sums, differences and negations representable. Input is owned.
template <typename T>
std::vector<std::tuple<T, int, int>> manhattan_edges(std::vector<T> xs,
std::vector<T> ys) {
assert(xs.size() == ys.size());
assert(xs.size() <= std::size_t(std::numeric_limits<int>::max()));
using W = std::conditional_t<std::numeric_limits<T>::is_integer,
std::conditional_t<(sizeof(T) < 8), std::int64_t,
std::conditional_t<(sizeof(T) == 8), __int128, T>>, T>;
static_assert(!std::numeric_limits<W>::is_integer ||
std::numeric_limits<W>::is_signed);
auto widen = [](std::vector<T> v) {
if constexpr (std::is_same_v<T, W>) return v;
else return std::vector<W>(v.begin(), v.end());
};
auto x = widen(std::move(xs)), y = widen(std::move(ys));
const int n = int(x.size());
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), 0);
std::vector<std::tuple<T, int, int>> ret;
ret.reserve(4 * std::size_t(n));
std::vector<W> sum(n);
for (int s = 0; s < 2; s++) {
for (int t = 0; t < 2; t++) {
for (int i = 0; i < n; ++i) sum[i] = x[i] + y[i];
std::sort(idx.begin(), idx.end(),
[&](int i, int j) { return sum[i] < sum[j]; });
std::map<W, int> src;
for (int i : idx) {
auto it = src.lower_bound(-y[i]);
while (it != src.end()) {
int j = it->second;
W dx = x[i] - x[j], dy = y[i] - y[j];
if (dx < dy) break;
// The sweep guarantees dx >= dy >= 0.
W weight = dx + dy;
assert(weight >= 0 && weight <= W(std::numeric_limits<T>::max()));
ret.emplace_back(T(weight), i, j);
it = src.erase(it);
}
// Reuse the scan's insertion position and preserve key replacement.
src.emplace_hint(it, -y[i], i)->second = i;
}
std::swap(x, y);
}
for (auto &v : x) v = -v;
}
std::sort(ret.begin(), ret.end());
return ret;
}
template <typename PointType>
auto manhattan_edges(const std::vector<PointType> &pt) {
using CoordType = std::decay_t<decltype(std::get<0>(pt[0]))>;
std::vector<CoordType> xs, ys;
xs.reserve(pt.size());
ys.reserve(pt.size());
for (const auto &pts : pt) {
xs.push_back(std::get<0>(pts));
ys.push_back(std::get<1>(pts));
}
return manhattan_edges(std::move(xs), std::move(ys));
}
} // namespace noya
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
struct bicriteria_spanning_tree_result {
std::int64_t s1 = 0;
std::int64_t s2 = 0;
std::vector<int> eid;
};
/// @brief Minimize (sum wa)*(sum wb) on a connected undirected graph.
/// Non-loop weights must be nonnegative. Loops are ignored; parallel edges
/// keep their original IDs. Require n>=1, valid endpoints, at most INT_MAX
/// edges, and both component sums of every queried MST representable by int64.
/// Supported-point search uses Q input-dependent MST queries, not a fixed
/// number of rounds. Preserve original scalarized-cost/edge-ID tie decisions.
inline bicriteria_spanning_tree_result minimum_product_spanning_tree(
int n,
const std::vector<std::tuple<std::int64_t, std::int64_t, int, int>> &es) {
assert(n >= 1 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
struct record { __int128 key; int id; };
std::vector<record> order;
for (int id = 0; id < int(es.size()); ++id) {
const auto &[wa, wb, u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
assert(wa >= 0 && wb >= 0);
order.push_back({0, id});
}
if (n == 1) return {};
using point = std::pair<std::int64_t, std::int64_t>;
auto product = [](point p) { return __int128(p.first) * p.second; };
auto less = [](const record &a, const record &b) {
return a.key != b.key ? a.key < b.key : a.id < b.id;
};
bicriteria_spanning_tree_result current;
current.eid.reserve(n - 1);
auto tree = [&](std::int64_t ca, std::int64_t cb) -> point {
for (auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
item.key = __int128(ca) * a + __int128(cb) * b;
}
if (!std::is_sorted(order.begin(), order.end(), less))
std::sort(order.begin(), order.end(), less);
atcoder::dsu dsu(n);
current.eid.clear();
__int128 a_sum = 0, b_sum = 0;
for (const auto &item : order) {
const auto &[a, b, u, v] = es[item.id];
int x = dsu.leader(u), y = dsu.leader(v);
if (x == y) continue;
dsu.merge(x, y);
a_sum += a; b_sum += b;
current.eid.push_back(item.id);
if (int(current.eid.size()) == n - 1) break;
}
assert(int(current.eid.size()) == n - 1);
assert(a_sum <= std::numeric_limits<std::int64_t>::max());
assert(b_sum <= std::numeric_limits<std::int64_t>::max());
current.s1 = std::int64_t(a_sum); current.s2 = std::int64_t(b_sum);
return {current.s1, current.s2};
};
auto x = tree(1, 0);
auto best = current;
auto y = tree(0, 1);
if (product(y) <= product(x)) best = current;
// Recursion retains only two-coordinate points; the query buffers are shared.
auto search = [&](auto &self, point l, point r) -> void {
// This hull interval lies in [l.first,r.first] x [r.second,l.second].
if (__int128(l.first) * r.second >= product({best.s1, best.s2})) return;
std::int64_t ca = l.second - r.second, cb = r.first - l.first;
auto mid = tree(ca, cb);
__int128 bound = __int128(ca) * l.first + __int128(cb) * l.second;
__int128 value = __int128(ca) * mid.first + __int128(cb) * mid.second;
if (value >= bound) return;
if (product(mid) < product({best.s1, best.s2})) best = current;
self(self, l, mid);
self(self, mid, r);
};
search(search, x, y);
return best;
}
/// @brief Chebyshev-distance MST of integer points in O(n log(n+1)) time.
/// Return (int64 total, original point-index pairs). Empty/single inputs cost 0;
/// duplicate points are allowed, input is unchanged, and tied optimum trees
/// may differ from complete-graph Kruskal. Endpoints in each pair are increasing.
/// Coordinates may span int64; the resulting total must fit int64.
inline std::pair<std::int64_t, std::vector<std::pair<int, int>>>
chebyshev_mst(const std::vector<std::pair<std::int64_t, std::int64_t>> &pt) {
assert(pt.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(pt.size());
if (n <= 1) return {0, {}};
std::vector<__int128> x, y;
x.reserve(n); y.reserve(n);
for (auto [a, b] : pt) {
x.push_back(__int128(a) + b);
y.push_back(__int128(a) - b);
}
// |dx+dy|+|dx-dy| = 2*max(|dx|,|dy|); transformed distances are even.
auto edges = manhattan_edges(std::move(x), std::move(y));
atcoder::dsu dsu(n);
__int128 cost = 0;
std::vector<std::pair<int, int>> result;
result.reserve(n - 1);
for (auto [distance, a, b] : edges) {
int u = dsu.leader(a), v = dsu.leader(b);
if (u == v) continue;
dsu.merge(u, v);
assert(distance % 2 == 0);
cost += distance / 2;
if (a > b) std::swap(a, b);
result.emplace_back(a, b);
if (int(result.size()) == n - 1) break;
}
assert(int(result.size()) == n - 1);
assert(cost <= std::numeric_limits<std::int64_t>::max());
return {std::int64_t(cost), std::move(result)};
}
} // namespace noya
// NOYA_SPECIAL_SPANNING_TREES_HPP