rooted_tree_minimum_inversion_order.hpp¶
对非负权 c、d，求父亲在孩子之前且 sum(i<j) d[ord[i]]*c[ord[j]] 最小的排列；按块的 c/d 收缩到父块，用路径压缩和环形链表恢复顺序，\(O(n\log n)\)。
Complexity: Time: \(O(n \log (n + 1))\) with constant-time Weight arithmetic. Space: \(O(n)\), including worst-case \(O(n)\) path-compression recursion.
AC 记录：rooted_tree_topological_order_with_minimum_inversions。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log(n+1)) with constant-time Weight arithmetic.
/// Space: O(n), including worst-case O(n) path-compression recursion.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A path-compressed parent link finds that block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums, products and the cost.
/// fa must describe one nonempty tree, with exactly one -1 root. Inputs are
/// unchanged. Equal ratios prefer the larger block root, then version;
/// (c,d) == (0,0) has lower priority than every nonzero block.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
bool operator()(const block &l, const block &r) const {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) return lz;
if (!lz) {
Weight lhs = l.c * r.d, rhs = l.d * r.c;
if (lhs < rhs) return true;
if (rhs < lhs) return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::vector<block> initial;
initial.reserve(siz - 1);
for (int u = 0; u < siz; u++) {
if (u != rt) {
initial.push_back({bd[u], bc[u], u, 0});
}
}
std::priority_queue<block, std::vector<block>, lower_priority> q(
lower_priority{}, std::move(initial));
std::vector<int> link(siz);
std::iota(link.begin(), link.end(), 0);
auto leader = [&](auto &self, int u) -> int {
return link[u] == u ? u : link[u] = self(self, link[u]);
};
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
for (int merged = 0; merged < siz - 1;) {
assert(!q.empty());
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = leader(leader, fa[u]);
link[u] = bp; // A live block's representative is its highest vertex.
++merged;
if (bp != rt) {
bc[bp] += bc[u];
bd[bp] += bd[u];
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.resize(siz);
int u = rt;
for (int i = siz - 1; i >= 0; --i) {
u = nxt[u];
res.ord[i] = u;
}
assert(u == rt);
Weight pd{};
for (int i = 0; i < siz; ++i) {
int cur = res.ord[i];
res.cst += pd * c[cur];
if (i + 1 < siz) pd += d[cur];
}
return res;
}
} // namespace noya
// NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP
#ifndef NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP
#define NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP 1
/// @complexity Time: O(n log(n+1)) with constant-time Weight arithmetic.
/// Space: O(n), including worst-case O(n) path-compression recursion.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A path-compressed parent link finds that block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums, products and the cost.
/// fa must describe one nonempty tree, with exactly one -1 root. Inputs are
/// unchanged. Equal ratios prefer the larger block root, then version;
/// (c,d) == (0,0) has lower priority than every nonzero block.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
bool operator()(const block &l, const block &r) const {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) return lz;
if (!lz) {
Weight lhs = l.c * r.d, rhs = l.d * r.c;
if (lhs < rhs) return true;
if (rhs < lhs) return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::vector<block> initial;
initial.reserve(siz - 1);
for (int u = 0; u < siz; u++) {
if (u != rt) {
initial.push_back({bd[u], bc[u], u, 0});
}
}
std::priority_queue<block, std::vector<block>, lower_priority> q(
lower_priority{}, std::move(initial));
std::vector<int> link(siz);
std::iota(link.begin(), link.end(), 0);
auto leader = [&](auto &self, int u) -> int {
return link[u] == u ? u : link[u] = self(self, link[u]);
};
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
for (int merged = 0; merged < siz - 1;) {
assert(!q.empty());
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = leader(leader, fa[u]);
link[u] = bp; // A live block's representative is its highest vertex.
++merged;
if (bp != rt) {
bc[bp] += bc[u];
bd[bp] += bd[u];
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.resize(siz);
int u = rt;
for (int i = siz - 1; i >= 0; --i) {
u = nxt[u];
res.ord[i] = u;
}
assert(u == rt);
Weight pd{};
for (int i = 0; i < siz; ++i) {
int cur = res.ord[i];
res.cst += pd * c[cur];
if (i + 1 < siz) pd += d[cur];
}
return res;
}
} // namespace noya
#endif // NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP
/// @complexity Time: O(n log(n+1)) with constant-time Weight arithmetic.
/// Space: O(n), including worst-case O(n) path-compression recursion.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A path-compressed parent link finds that block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums, products and the cost.
/// fa must describe one nonempty tree, with exactly one -1 root. Inputs are
/// unchanged. Equal ratios prefer the larger block root, then version;
/// (c,d) == (0,0) has lower priority than every nonzero block.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
bool operator()(const block &l, const block &r) const {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) return lz;
if (!lz) {
Weight lhs = l.c * r.d, rhs = l.d * r.c;
if (lhs < rhs) return true;
if (rhs < lhs) return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::vector<block> initial;
initial.reserve(siz - 1);
for (int u = 0; u < siz; u++) {
if (u != rt) {
initial.push_back({bd[u], bc[u], u, 0});
}
}
std::priority_queue<block, std::vector<block>, lower_priority> q(
lower_priority{}, std::move(initial));
std::vector<int> link(siz);
std::iota(link.begin(), link.end(), 0);
auto leader = [&](auto &self, int u) -> int {
return link[u] == u ? u : link[u] = self(self, link[u]);
};
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
for (int merged = 0; merged < siz - 1;) {
assert(!q.empty());
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = leader(leader, fa[u]);
link[u] = bp; // A live block's representative is its highest vertex.
++merged;
if (bp != rt) {
bc[bp] += bc[u];
bd[bp] += bd[u];
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.resize(siz);
int u = rt;
for (int i = siz - 1; i >= 0; --i) {
u = nxt[u];
res.ord[i] = u;
}
assert(u == rt);
Weight pd{};
for (int i = 0; i < siz; ++i) {
int cur = res.ord[i];
res.cst += pd * c[cur];
if (i + 1 < siz) pd += d[cur];
}
return res;
}
} // namespace noya
// NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP