dynamic_star_min_cut.hpp¶
固定非负无向图外加中心点，维护星形边权修改后的全局最小割；收缩建树、树上差分和免下推的区间加最小值。
Complexity: Time: \(O(n (n + m) \log (n + m + 1))\) preprocessing, \(O(\log^{2} (n + 1))\) per update, \(O(1)\) query. Space: \(O(n + m)\) build, \(O(n)\) retained. For simple graphs, preprocessing is \(O(n (n + m) \log (n + 1))\).
Source: Library Checker
AC 记录：global_minimum_cut_of_dynamic_star_augmented_graph。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n(n+m) log(n+m+1)) preprocessing,
/// O(log^2(n+1)) per update, O(1) query. Space: O(n+m) build, O(n) retained.
/// For simple graphs, preprocessing is O(n(n+m) log(n+1)).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
// mn includes this node's lazy value but excludes its ancestors' values.
// Common additions commute with min, so partial updates need no push.
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
int mid = (l + r) / 2;
if (ql < mid)
add(ql, qr, 2 * nd + 1, l, mid, ad1);
if (mid < qr)
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = lz[nd] + std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * std::size_t(siz) - 1, inf);
lz.assign(mn.size(), 0);
}
void build(const std::vector<i64> &a) {
assert(a.size() <= std::size_t(siz));
std::fill(mn.begin(), mn.end(), inf);
std::fill(lz.begin(), lz.end(), 0);
std::copy(a.begin(), a.end(), mn.begin() + siz - 1);
for (int i = siz - 2; i >= 0; --i)
mn[i] = std::min(mn[2 * i + 1], mn[2 * i + 2]);
}
void add(int l, int r, i64 ad1) {
if (l < r && ad1 != 0)
add(l, r, 0, 0, siz, ad1);
}
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
g.resize(2 * n - 1);
std::vector<int> active(n);
for (int u = 0; u < n; ++u)
active[u] = u;
std::vector<char> vis(2 * n - 1);
std::vector<i64> es(2 * n - 1);
using heap_entry = std::pair<i64, int>;
for (int mer = n; mer < 2 * n - 1; ++mer) {
std::vector<heap_entry> init;
init.reserve(active.size());
for (int u : active) {
vis[u] = false;
es[u] = 0;
for (auto e : g[u])
es[u] += e.w;
init.push_back({-es[u], u});
}
std::priority_queue<heap_entry> q(std::less<heap_entry>{}, std::move(init));
int a = -1, b = -1;
for (std::size_t pos = 0; pos < active.size(); ++pos) {
int u;
do {
u = q.top().second;
q.pop();
} while (vis[u]);
vis[u] = true;
b = a;
a = u;
for (auto e : g[u])
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
// Clear capacity too: retired clusters must not retain O(n*m) buffers.
std::vector<weighted_neighbor>().swap(g[a]);
std::vector<weighted_neighbor>().swap(g[b]);
std::size_t keep = 0;
for (int u : active) {
if (u == a || u == b)
continue;
active[keep++] = u;
i64 sum = 0;
std::size_t ptr = 0;
for (auto e : g[u]) {
if (e.u == a || e.u == b)
sum += e.w;
else
g[u][ptr++] = e;
}
g[u].resize(ptr);
if (sum) {
g[u].push_back({mer, sum});
g[mer].push_back({u, sum});
}
}
active.resize(keep);
active.push_back(mer);
tr[mer] = {a, b};
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut. Vertices are [0,n); require 1 <= n <= INT_MAX/4.
/// Edges and star weights are nonnegative. Parallel edges are allowed; loops
/// are ignored. Require the sum of all non-loop edge weights and current star
/// weights to stay below 2^60 (also at construction). This bounds all int64
/// intermediates and keeps real cuts below the segment tree's padding value.
/// Construction leaves inputs unchanged. Copies own independent state.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<int> fa, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
static int tree_size(int n) {
assert(1 <= n && n <= std::numeric_limits<int>::max() / 4);
return 2 * n - 1;
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), fa(tree_size(n), -1), hd(fa.size()),
ord(fa.size()), mn(int(fa.size())) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (a != b && w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
auto tr =
dynamic_star_min_cut_internal::build_contraction_tree(std::move(g));
std::vector<int> dep(2 * n - 1), son(2 * n - 1, -1);
int rt = 2 * n - 2;
// Every contraction parent has a larger id than both children.
// Sizes accumulate forwards; depths propagate backwards, without DFS.
std::vector<int> sz(2 * n - 1, 1);
for (int u = n; u <= rt; ++u) {
for (int v : tr[u]) {
fa[v] = u;
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]])
son[u] = v;
}
}
for (int u = rt; u >= n; --u)
for (int v : tr[u])
dep[v] = dep[u] + 1;
int ptr = 0;
std::vector<int> queue{rt};
for (std::size_t i = 0; i < queue.size(); ++i) {
int ch = queue[i];
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u])
if (v != son[u])
queue.push_back(v);
}
}
// An edge contributes at both leaves and -2*w at their LCA. Forward
// accumulation yields each cluster boundary plus its star-weight sum.
std::vector<i64> bd(2 * n - 1);
for (int u = 0; u < n; ++u) {
assert(wt[u] >= 0);
bd[u] = wt[u];
}
for (auto [a, b, w] : es1) {
if (a == b || w == 0)
continue;
bd[a] += w;
bd[b] += w;
int l = a, r = b;
while (hd[l] != hd[r]) {
if (dep[hd[l]] < dep[hd[r]])
std::swap(l, r);
l = fa[hd[l]];
}
bd[dep[l] < dep[r] ? l : r] -= 2 * w;
}
for (int u = 0; u < rt; ++u)
bd[fa[u]] += bd[u];
std::vector<i64> init(2 * n - 1);
for (int u = 0; u <= rt; ++u)
init[ord[u]] = bd[u];
mn.build(init);
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
if (w == wt[u])
return mn.all_min();
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya
// NOYA_DYNAMIC_STAR_MIN_CUT_HPP
#ifndef NOYA_DYNAMIC_STAR_MIN_CUT_HPP
#define NOYA_DYNAMIC_STAR_MIN_CUT_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n(n+m) log(n+m+1)) preprocessing,
/// O(log^2(n+1)) per update, O(1) query. Space: O(n+m) build, O(n) retained.
/// For simple graphs, preprocessing is O(n(n+m) log(n+1)).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
// mn includes this node's lazy value but excludes its ancestors' values.
// Common additions commute with min, so partial updates need no push.
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
int mid = (l + r) / 2;
if (ql < mid)
add(ql, qr, 2 * nd + 1, l, mid, ad1);
if (mid < qr)
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = lz[nd] + std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * std::size_t(siz) - 1, inf);
lz.assign(mn.size(), 0);
}
void build(const std::vector<i64> &a) {
assert(a.size() <= std::size_t(siz));
std::fill(mn.begin(), mn.end(), inf);
std::fill(lz.begin(), lz.end(), 0);
std::copy(a.begin(), a.end(), mn.begin() + siz - 1);
for (int i = siz - 2; i >= 0; --i)
mn[i] = std::min(mn[2 * i + 1], mn[2 * i + 2]);
}
void add(int l, int r, i64 ad1) {
if (l < r && ad1 != 0)
add(l, r, 0, 0, siz, ad1);
}
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
g.resize(2 * n - 1);
std::vector<int> active(n);
for (int u = 0; u < n; ++u)
active[u] = u;
std::vector<char> vis(2 * n - 1);
std::vector<i64> es(2 * n - 1);
using heap_entry = std::pair<i64, int>;
for (int mer = n; mer < 2 * n - 1; ++mer) {
std::vector<heap_entry> init;
init.reserve(active.size());
for (int u : active) {
vis[u] = false;
es[u] = 0;
for (auto e : g[u])
es[u] += e.w;
init.push_back({-es[u], u});
}
std::priority_queue<heap_entry> q(std::less<heap_entry>{}, std::move(init));
int a = -1, b = -1;
for (std::size_t pos = 0; pos < active.size(); ++pos) {
int u;
do {
u = q.top().second;
q.pop();
} while (vis[u]);
vis[u] = true;
b = a;
a = u;
for (auto e : g[u])
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
// Clear capacity too: retired clusters must not retain O(n*m) buffers.
std::vector<weighted_neighbor>().swap(g[a]);
std::vector<weighted_neighbor>().swap(g[b]);
std::size_t keep = 0;
for (int u : active) {
if (u == a || u == b)
continue;
active[keep++] = u;
i64 sum = 0;
std::size_t ptr = 0;
for (auto e : g[u]) {
if (e.u == a || e.u == b)
sum += e.w;
else
g[u][ptr++] = e;
}
g[u].resize(ptr);
if (sum) {
g[u].push_back({mer, sum});
g[mer].push_back({u, sum});
}
}
active.resize(keep);
active.push_back(mer);
tr[mer] = {a, b};
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut. Vertices are [0,n); require 1 <= n <= INT_MAX/4.
/// Edges and star weights are nonnegative. Parallel edges are allowed; loops
/// are ignored. Require the sum of all non-loop edge weights and current star
/// weights to stay below 2^60 (also at construction). This bounds all int64
/// intermediates and keeps real cuts below the segment tree's padding value.
/// Construction leaves inputs unchanged. Copies own independent state.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<int> fa, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
static int tree_size(int n) {
assert(1 <= n && n <= std::numeric_limits<int>::max() / 4);
return 2 * n - 1;
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), fa(tree_size(n), -1), hd(fa.size()),
ord(fa.size()), mn(int(fa.size())) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (a != b && w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
auto tr =
dynamic_star_min_cut_internal::build_contraction_tree(std::move(g));
std::vector<int> dep(2 * n - 1), son(2 * n - 1, -1);
int rt = 2 * n - 2;
// Every contraction parent has a larger id than both children.
// Sizes accumulate forwards; depths propagate backwards, without DFS.
std::vector<int> sz(2 * n - 1, 1);
for (int u = n; u <= rt; ++u) {
for (int v : tr[u]) {
fa[v] = u;
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]])
son[u] = v;
}
}
for (int u = rt; u >= n; --u)
for (int v : tr[u])
dep[v] = dep[u] + 1;
int ptr = 0;
std::vector<int> queue{rt};
for (std::size_t i = 0; i < queue.size(); ++i) {
int ch = queue[i];
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u])
if (v != son[u])
queue.push_back(v);
}
}
// An edge contributes at both leaves and -2*w at their LCA. Forward
// accumulation yields each cluster boundary plus its star-weight sum.
std::vector<i64> bd(2 * n - 1);
for (int u = 0; u < n; ++u) {
assert(wt[u] >= 0);
bd[u] = wt[u];
}
for (auto [a, b, w] : es1) {
if (a == b || w == 0)
continue;
bd[a] += w;
bd[b] += w;
int l = a, r = b;
while (hd[l] != hd[r]) {
if (dep[hd[l]] < dep[hd[r]])
std::swap(l, r);
l = fa[hd[l]];
}
bd[dep[l] < dep[r] ? l : r] -= 2 * w;
}
for (int u = 0; u < rt; ++u)
bd[fa[u]] += bd[u];
std::vector<i64> init(2 * n - 1);
for (int u = 0; u <= rt; ++u)
init[ord[u]] = bd[u];
mn.build(init);
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
if (w == wt[u])
return mn.all_min();
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya
#endif // NOYA_DYNAMIC_STAR_MIN_CUT_HPP
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n(n+m) log(n+m+1)) preprocessing,
/// O(log^2(n+1)) per update, O(1) query. Space: O(n+m) build, O(n) retained.
/// For simple graphs, preprocessing is O(n(n+m) log(n+1)).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
// mn includes this node's lazy value but excludes its ancestors' values.
// Common additions commute with min, so partial updates need no push.
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
int mid = (l + r) / 2;
if (ql < mid)
add(ql, qr, 2 * nd + 1, l, mid, ad1);
if (mid < qr)
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = lz[nd] + std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * std::size_t(siz) - 1, inf);
lz.assign(mn.size(), 0);
}
void build(const std::vector<i64> &a) {
assert(a.size() <= std::size_t(siz));
std::fill(mn.begin(), mn.end(), inf);
std::fill(lz.begin(), lz.end(), 0);
std::copy(a.begin(), a.end(), mn.begin() + siz - 1);
for (int i = siz - 2; i >= 0; --i)
mn[i] = std::min(mn[2 * i + 1], mn[2 * i + 2]);
}
void add(int l, int r, i64 ad1) {
if (l < r && ad1 != 0)
add(l, r, 0, 0, siz, ad1);
}
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
g.resize(2 * n - 1);
std::vector<int> active(n);
for (int u = 0; u < n; ++u)
active[u] = u;
std::vector<char> vis(2 * n - 1);
std::vector<i64> es(2 * n - 1);
using heap_entry = std::pair<i64, int>;
for (int mer = n; mer < 2 * n - 1; ++mer) {
std::vector<heap_entry> init;
init.reserve(active.size());
for (int u : active) {
vis[u] = false;
es[u] = 0;
for (auto e : g[u])
es[u] += e.w;
init.push_back({-es[u], u});
}
std::priority_queue<heap_entry> q(std::less<heap_entry>{}, std::move(init));
int a = -1, b = -1;
for (std::size_t pos = 0; pos < active.size(); ++pos) {
int u;
do {
u = q.top().second;
q.pop();
} while (vis[u]);
vis[u] = true;
b = a;
a = u;
for (auto e : g[u])
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
// Clear capacity too: retired clusters must not retain O(n*m) buffers.
std::vector<weighted_neighbor>().swap(g[a]);
std::vector<weighted_neighbor>().swap(g[b]);
std::size_t keep = 0;
for (int u : active) {
if (u == a || u == b)
continue;
active[keep++] = u;
i64 sum = 0;
std::size_t ptr = 0;
for (auto e : g[u]) {
if (e.u == a || e.u == b)
sum += e.w;
else
g[u][ptr++] = e;
}
g[u].resize(ptr);
if (sum) {
g[u].push_back({mer, sum});
g[mer].push_back({u, sum});
}
}
active.resize(keep);
active.push_back(mer);
tr[mer] = {a, b};
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut. Vertices are [0,n); require 1 <= n <= INT_MAX/4.
/// Edges and star weights are nonnegative. Parallel edges are allowed; loops
/// are ignored. Require the sum of all non-loop edge weights and current star
/// weights to stay below 2^60 (also at construction). This bounds all int64
/// intermediates and keeps real cuts below the segment tree's padding value.
/// Construction leaves inputs unchanged. Copies own independent state.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<int> fa, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
static int tree_size(int n) {
assert(1 <= n && n <= std::numeric_limits<int>::max() / 4);
return 2 * n - 1;
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), fa(tree_size(n), -1), hd(fa.size()),
ord(fa.size()), mn(int(fa.size())) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (a != b && w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
auto tr =
dynamic_star_min_cut_internal::build_contraction_tree(std::move(g));
std::vector<int> dep(2 * n - 1), son(2 * n - 1, -1);
int rt = 2 * n - 2;
// Every contraction parent has a larger id than both children.
// Sizes accumulate forwards; depths propagate backwards, without DFS.
std::vector<int> sz(2 * n - 1, 1);
for (int u = n; u <= rt; ++u) {
for (int v : tr[u]) {
fa[v] = u;
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]])
son[u] = v;
}
}
for (int u = rt; u >= n; --u)
for (int v : tr[u])
dep[v] = dep[u] + 1;
int ptr = 0;
std::vector<int> queue{rt};
for (std::size_t i = 0; i < queue.size(); ++i) {
int ch = queue[i];
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u])
if (v != son[u])
queue.push_back(v);
}
}
// An edge contributes at both leaves and -2*w at their LCA. Forward
// accumulation yields each cluster boundary plus its star-weight sum.
std::vector<i64> bd(2 * n - 1);
for (int u = 0; u < n; ++u) {
assert(wt[u] >= 0);
bd[u] = wt[u];
}
for (auto [a, b, w] : es1) {
if (a == b || w == 0)
continue;
bd[a] += w;
bd[b] += w;
int l = a, r = b;
while (hd[l] != hd[r]) {
if (dep[hd[l]] < dep[hd[r]])
std::swap(l, r);
l = fa[hd[l]];
}
bd[dep[l] < dep[r] ? l : r] -= 2 * w;
}
for (int u = 0; u < rt; ++u)
bd[fa[u]] += bd[u];
std::vector<i64> init(2 * n - 1);
for (int u = 0; u <= rt; ++u)
init[ord[u]] = bd[u];
mn.build(init);
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
if (w == wt[u])
return mn.all_min();
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya
// NOYA_DYNAMIC_STAR_MIN_CUT_HPP