Given two weighted, undirected graphs on $n$ nodes $G_1$ and $G_2$, is it possible to efficiently find a tree on these $n$ nodes that is an MST of both $G_1$ and $G_2$?↵
↵
**UPD:** Building on [user:chromate00,2026-04-23]'s comments, it turns out that we can simply construct a new graph $G$ where the weight of each edge is the sum of that edge's weights in $G_1$ and $G_2$, and find the MST on this graph (in [user:chromate00,2026-04-23]'s notation [here](https://mirror.codeforces.com/blog/entry/144898?#comment-1295911), this means we can actually just always set $C = 1$). If a common MST exists, we can guarantee that this algorithm will always find it.↵
↵
_Proof._ Let $W_1$, $W_2$, and $W$ denote the total weight of MSTs for $G_1$, $G_2$, and $G$ respectively. ↵
↵
- Note that $W_1 + W_2 \leq W$. ↵
- Also note that the weight of any spanning tree in $G_1$ is at least $W_1$, and similarly for $G_2$. Therefore, if we find a spanning tree $T$ with exactly $W = W_1 + W_2$, it must follow that $T$ has exactly weight $W_1$ in $G_1$ and exactly weight $W_2$ in $G_2$, since these are the minimum possible.↵
↵
Here's a problem that uses this idea: [problem:1054G]↵
↵
<spoiler summary="Hint">↵
How can we reframe the problem as finding a simultaneous MST for $m$ graphs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For convenience we will use MST = maximum spanning tree, but all the same principles still apply.↵
↵
For the $i$th community, let $G_i$ be the weighted complete graph in which edge $(u, v)$ has weight 1 if both $u$ and $v$ are in the $i$th community, and weight $0$ otherwise. Then, it is necessary and sufficient that the final tree be a MST ( **maximum** spanning tree) of $G_i$. Therefore, we want to find a simultaneous MST over all $G_i$.↵
↵
From here, we easily arrive at the MST solution given in the [official editorial](https://mirror.codeforces.com/blog/entry/62563) by creating a new graph that sums edge weights across all $G_i$ and finding its MST.↵
</spoiler>↵
↵
(This writeup is also available on my [personal blog](https://danielz.fyi/thoughts/mst)!)
↵
**UPD:** Building on [user:chromate00,2026-04-23]'s comments, it turns out that we can simply construct a new graph $G$ where the weight of each edge is the sum of that edge's weights in $G_1$ and $G_2$, and find the MST on this graph (in [user:chromate00,2026-04-23]'s notation [here](https://mirror.codeforces.com/blog/entry/144898?#comment-1295911), this means we can actually just always set $C = 1$). If a common MST exists, we can guarantee that this algorithm will always find it.↵
↵
_Proof._ Let $W_1$, $W_2$, and $W$ denote the total weight of MSTs for $G_1$, $G_2$, and $G$ respectively. ↵
↵
- Note that $W_1 + W_2 \leq W$. ↵
- Also note that the weight of any spanning tree in $G_1$ is at least $W_1$, and similarly for $G_2$. Therefore, if we find a spanning tree $T$ with exactly $W = W_1 + W_2$, it must follow that $T$ has exactly weight $W_1$ in $G_1$ and exactly weight $W_2$ in $G_2$, since these are the minimum possible.↵
↵
Here's a problem that uses this idea: [problem:1054G]↵
↵
<spoiler summary="Hint">↵
How can we reframe the problem as finding a simultaneous MST for $m$ graphs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For convenience we will use MST = maximum spanning tree, but all the same principles still apply.↵
↵
For the $i$th community, let $G_i$ be the weighted complete graph in which edge $(u, v)$ has weight 1 if both $u$ and $v$ are in the $i$th community, and weight $0$ otherwise. Then, it is necessary and sufficient that the final tree be a MST ( **maximum** spanning tree) of $G_i$. Therefore, we want to find a simultaneous MST over all $G_i$.↵
↵
From here, we easily arrive at the MST solution given in the [official editorial](https://mirror.codeforces.com/blog/entry/62563) by creating a new graph that sums edge weights across all $G_i$ and finding its MST.↵
</spoiler>↵
↵
(This writeup is also available on my [personal blog](https://danielz.fyi/thoughts/mst)!)
