**Context:**↵
<br>↵
I recently learnt MST and reached this problem ([problem:609E]). I was stuck on it for like 2 days, and I only managed to come up with an $O(m\log_m + mn)$ solution, which will obviously TLE. I decided to read some of my teachers'/friends'/top coders' codes to get some idea, but they all used some kind of heavy algorithm I haven't learnt yet (mostly LCA). I was ready to give up on the problem; I decided to hand-run the current algorithm I had one more time to look for improvements before giving up, and fortunately during hand-running I noticed a key property in the Kruskal algorithm which led to me coming up with an extremely clean sol.↵
<br>↵
It solves the problem in $O(m\log_m + (n + m\log_n)\log_n)$ and uses the core [Kruskal Algorithm](https://cp-algorithms.com/graph/mst_kruskal.html) plus a vector-based [StoL DSU](https://codeforces.me/blog/entry/67696).↵
<br>↵
IDK if this is a well-known property or not, but after checking some submissions, I'm sure it's not a well-known approach for this problem.↵
↵
--------------------------↵
↵
<spoiler summary="The Property">↵
During the Kruskal algorithm, at any point, the maximum-weighted edge between any $u$ and $v$ (obviously belonging to the same component) is the weight of the edge that merged their two components.↵
↵
<spoiler summary="Proof">↵
↵
- During the Kruskal algorithm, only edges that merge two disjoint components become part of the MST.↵
- Also, during the Kruskal algorithm, after $u$'s component and $v$'s component get merged, none of the added edges will end up on $u$–$v$'s path.↵
↵
Using the two facts above, and the fact that we process edges in sorted order, we can conclude the property.↵
</spoiler>↵
↵
</spoiler>↵
↵
-------------------------↵
↵
<spoiler summary="Full Solution">↵
Consider the MST for the graph. Now, for each edge $e = \{u, v, w\}$, add it to the MST. Now the MST has only one cycle, containing the path between $u$ and $v$ plus edge $e$. Since the structure of the MST except the cycle is still intact, we only have to remove one edge from the cycle to restore the tree structure. Since the question asks for the minimum sum of weights (while containing edge $e$), we can remove the maximum-weighted edge from the cycle, not including edge $e$, to get the MST containing edge $e$.↵
↵
If we implement this naively (like my original sol using DFS, [submission:389622797]) we will have an $O(m\log_m + mn)$ solution, which will unfortunately TLE, as discussed before. :(↵
↵
But we can use the property discussed above to reach an acceptable solution:↵
↵
For each edge $e = \{u, v, w\}$ we can pre-calculate the maximum-weighted edge between $u$ and $v$'s path, with weight $mxw$. Then the answer for $e$ becomes:↵
↵
$$\text{(sum of weights in MST)} - mxw + w$$↵
↵
And for the pre-calculation we use the property described above + StoL vector-based DSU — when merging two trees in the Kruskal algorithm, we set $mxw$ for all the edges between the two components to $w$.↵
↵
For a better understanding of the pre-calc itself, view the implementation, and for a better understanding of its complexity, view the source linked for StoL DSU.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
#define fi first↵
#define se second↵
#define pb push_back↵
↵
#define Fast ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);↵
#define Tests int tt; cin >> tt; while(tt--) input(), solve(), output();↵
#define Single input(), solve(), output();↵
↵
// ----------------------------------------------------- //↵
// █████╗ ██████╗ ██╗ ██╗ █████╗ ███╗ ██╗ //↵
// ██╔══██╗ ██╔══██╗ ╚██╗ ██╔╝ ██╔══██╗ ████╗ ██║ //↵
// ███████║ ██████╔╝ ╚████╔╝ ███████║ ██╔██╗ ██║ :): //↵
// ██╔══██║ ██╔══██╗ ╚██╔╝ ██╔══██║ ██║╚██╗██║ //↵
// ██║ ██║ ██║ ██║ ██║ ██║ ██║ ██║ ╚████║ //↵
// ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═══╝ //↵
// ----------------------------------------------------- //↵
// 0 1 2 3 4 5 6 7 8 9 | n = 10↵
↵
const int N = 2e5 + 5, M = 2e5 + 5;↵
struct edge {int u, v, w, idx;} ed[M];↵
vector<pair<int, int>> adj[N];↵
int n, m, id[N], mxw[M];↵
set<int> cmp[N];↵
ll mstw;↵
↵
void move(int v, int u, int w) { // move v to u↵
// handle edges between components↵
for (int x : cmp[v])↵
for (auto [y, idx] : adj[x])↵
if (cmp[u].count(y))↵
mxw[idx] = w;↵
↵
// move nodes from component v to u↵
for (int x : cmp[v]) {↵
id[x] = u;↵
cmp[u].insert(x);↵
}↵
cmp[v].clear();↵
}↵
↵
bool merge(edge x) {↵
int u = id[x.u];↵
int v = id[x.v];↵
↵
if (u == v)↵
return false;↵
↵
cmp[u].size() < cmp[v].size() ? move(u, v, x.w) : move(v, u, x.w);↵
return true;↵
}↵
↵
void input() {↵
cin >> n >> m;↵
for (int i = 0; i < m; i++) {↵
int u, v, w;↵
cin >> u >> v >> w;↵
u--, v--;↵
↵
ed[i] = {u, v, w, i};↵
adj[u].pb({v, i});↵
adj[v].pb({u, i});↵
}↵
}↵
↵
void solve() {↵
for (int u = 0; u < n; u++) {↵
cmp[u].insert(u);↵
id[u] = u;↵
}↵
↵
sort(ed, ed + m, [](const edge a, const edge b ) {↵
return a.w < b.w;↵
});↵
↵
for (int i = 0; i < m; i++)↵
mstw += (ll)ed[i].w * merge(ed[i]);↵
}↵
↵
↵
↵
void output() {↵
sort(ed, ed + m, [](const edge a, const edge b ) {↵
return a.idx < b.idx;↵
});↵
↵
for (int i = 0; i < m; i++)↵
cout << mstw - mxw[i] + ed[i].w << '\n';↵
}↵
↵
int main() {↵
Fast↵
// Tests↵
Single↵
}↵
~~~~~↵
</spoiler>↵
↵
--------------------------↵
↵
I'm new to CP and hand-wrote everything myself (I used AI just for notation and capitalization and stuff), so if anyone has a better way of explaining than I do, or if some of what I said is wrong or needs editing, please let me know and I will edit the blog to bring it up to standard.
<br>↵
I recently learnt MST and reached this problem ([problem:609E]). I was stuck on it for like 2 days, and I only managed to come up with an $O(m\log
<br>↵
It solves the problem in $O(m\log
<br>↵
IDK if this is a well-known property or not, but after checking some submissions, I'm sure it's not a well-known approach for this problem.↵
↵
--------------------------↵
↵
<spoiler summary="The Property">↵
During the Kruskal algorithm, at any point, the maximum-weighted edge between any $u$ and $v$ (obviously belonging to the same component) is the weight of the edge that merged their two components.↵
↵
<spoiler summary="Proof">↵
↵
- During the Kruskal algorithm, only edges that merge two disjoint components become part of the MST.↵
- Also, during the Kruskal algorithm, after $u$'s component and $v$'s component get merged, none of the added edges will end up on $u$–$v$'s path.↵
↵
Using the two facts above, and the fact that we process edges in sorted order, we can conclude the property.↵
</spoiler>↵
↵
</spoiler>↵
↵
-------------------------↵
↵
<spoiler summary="Full Solution">↵
Consider the MST for the graph. Now, for each edge $e = \{u, v, w\}$, add it to the MST. Now the MST has only one cycle, containing the path between $u$ and $v$ plus edge $e$. Since the structure of the MST except the cycle is still intact, we only have to remove one edge from the cycle to restore the tree structure. Since the question asks for the minimum sum of weights (while containing edge $e$), we can remove the maximum-weighted edge from the cycle, not including edge $e$, to get the MST containing edge $e$.↵
↵
If we implement this naively (like my original sol using DFS, [submission:389622797]) we will have an $O(m\log
↵
But we can use the property discussed above to reach an acceptable solution:↵
↵
For each edge $e = \{u, v, w\}$ we can pre-calculate the maximum-weighted edge between $u$ and $v$'s path, with weight $mxw$. Then the answer for $e$ becomes:↵
↵
$$\text{(sum of weights in MST)} - mxw + w$$↵
↵
And for the pre-calculation we use the property described above + StoL vector-based DSU — when merging two trees in the Kruskal algorithm, we set $mxw$ for all the edges between the two components to $w$.↵
↵
For a better understanding of the pre-calc itself, view the implementation, and for a better understanding of its complexity, view the source linked for StoL DSU.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
#define fi first↵
#define se second↵
#define pb push_back↵
↵
#define Fast ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);↵
#define Tests int tt; cin >> tt; while(tt--) input(), solve(), output();↵
#define Single input(), solve(), output();↵
↵
// ----------------------------------------------------- //↵
// █████╗ ██████╗ ██╗ ██╗ █████╗ ███╗ ██╗ //↵
// ██╔══██╗ ██╔══██╗ ╚██╗ ██╔╝ ██╔══██╗ ████╗ ██║ //↵
// ███████║ ██████╔╝ ╚████╔╝ ███████║ ██╔██╗ ██║ :): //↵
// ██╔══██║ ██╔══██╗ ╚██╔╝ ██╔══██║ ██║╚██╗██║ //↵
// ██║ ██║ ██║ ██║ ██║ ██║ ██║ ██║ ╚████║ //↵
// ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═══╝ //↵
// ----------------------------------------------------- //↵
// 0 1 2 3 4 5 6 7 8 9 | n = 10↵
↵
const int N = 2e5 + 5, M = 2e5 + 5;↵
struct edge {int u, v, w, idx;} ed[M];↵
vector<pair<int, int>> adj[N];↵
int n, m, id[N], mxw[M];↵
set<int> cmp[N];↵
ll mstw;↵
↵
void move(int v, int u, int w) { // move v to u↵
// handle edges between components↵
for (int x : cmp[v])↵
for (auto [y, idx] : adj[x])↵
if (cmp[u].count(y))↵
mxw[idx] = w;↵
↵
// move nodes from component v to u↵
for (int x : cmp[v]) {↵
id[x] = u;↵
cmp[u].insert(x);↵
}↵
cmp[v].clear();↵
}↵
↵
bool merge(edge x) {↵
int u = id[x.u];↵
int v = id[x.v];↵
↵
if (u == v)↵
return false;↵
↵
cmp[u].size() < cmp[v].size() ? move(u, v, x.w) : move(v, u, x.w);↵
return true;↵
}↵
↵
void input() {↵
cin >> n >> m;↵
for (int i = 0; i < m; i++) {↵
int u, v, w;↵
cin >> u >> v >> w;↵
u--, v--;↵
↵
ed[i] = {u, v, w, i};↵
adj[u].pb({v, i});↵
adj[v].pb({u, i});↵
}↵
}↵
↵
void solve() {↵
for (int u = 0; u < n; u++) {↵
cmp[u].insert(u);↵
id[u] = u;↵
}↵
↵
sort(ed, ed + m, [](const edge a, const edge b ) {↵
return a.w < b.w;↵
});↵
↵
for (int i = 0; i < m; i++)↵
mstw += (ll)ed[i].w * merge(ed[i]);↵
}↵
↵
↵
↵
void output() {↵
sort(ed, ed + m, [](const edge a, const edge b ) {↵
return a.idx < b.idx;↵
});↵
↵
for (int i = 0; i < m; i++)↵
cout << mstw - mxw[i] + ed[i].w << '\n';↵
}↵
↵
int main() {↵
Fast↵
// Tests↵
Single↵
}↵
~~~~~↵
</spoiler>↵
↵
--------------------------↵
↵
I'm new to CP and hand-wrote everything myself (I used AI just for notation and capitalization and stuff), so if anyone has a better way of explaining than I do, or if some of what I said is wrong or needs editing, please let me know and I will edit the blog to bring it up to standard.
