Day 125-Q4 | 次点全域木（Second Best Minimum Spanning Tree）

問題

$N$ 頂点 $M$ 辺の連結な無向グラフが与えられる（辺には重みがあり、多重辺・自己ループはない）。

最小全域木（MST）の重みの総和 $W$ を求めよ。
MSTと辺集合が異なる全域木の中で、重みの総和が最小のものの値 $W_2$ を求めよ（MSTが複数存在する場合、$W_2=W$ となり得る）。

入力形式

N M
u_1 v_1 w_1
...
u_M v_M w_M

制約

$2 \le N \le 100000$

$N-1 \le M \le 200000$

$1 \le u_i,v_i \le N,\ u_i\neq v_i$

$1 \le w_i \le 10^9$

グラフは連結

入出力例

入力例1

出力例1

6
8

MSTは(1,2,1),(2,3,2),(3,4,3)でW=6。非木辺(1,3,4)はパス最大辺2より大きく候補6-2+4=8。非木辺(1,4,5)はパス最大辺3より大きく候補6-3+5=8。W2=8

入力例2

出力例2

3
3

非木辺(1,3,2)はパス最大辺重み2と等しい→同重み置き換えで別のMSTができる→W2=W=3

概念図

ヒント（段階的開示）

ヒント1（方向性）

MSTに含まれない辺 $(u,v,w)$ を1本追加すると、木の中に $u$-$v$ 間のパスを含む閉路ができる。この閉路からMSTに含まれていた辺を1本取り除けば、また別の全域木になる。どの辺を取り除けば重みの増加が最小になるかを考える。

ヒント2（アプローチ）

最適な取り除き対象は「木上の $u$-$v$ パス上にある辺の中で最大重みのもの」。MSTのカット性質から、非木辺の重み $w$ は必ずその閉路上の最大辺重み以上になる。等しい場合、置き換えても総重みは変わらない別の全域木ができる＝そのままMSTと同じ重み $W$ が答え（それ以上小さくはならないため即座に確定してよい）。等しくなければ候補は $W - (\text{パス上の最大辺重み}) + w$。全非木辺の中でこの候補の最小値（または等号ケース）を答えとする。

ヒント3（誘導）

木上の任意の2頂点間パスの最大辺重みを高速に求めるには、LCAの二分累乗を「祖先ジャンプ＋そのジャンプで通過する辺の最大重み」も同時に管理する形に拡張する。

LOG = max(1, n.bit_length() + 1)
up = [[0] * (n + 1) for _ in range(LOG)]
mx = [[0] * (n + 1) for _ in range(LOG)]

for k in range(1, LOG):
    for v in range(1, n + 1):
        up[k][v] = up[k - 1][up[k - 1][v]]
        mx[k][v] = max(mx[k - 1][v], mx[k - 1][up[k - 1][v]])

模範解答 (Python)

import sys
from collections import deque


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    edges = []
    for i in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        edges.append((w, u, v))

    order = sorted(range(m), key=lambda i: edges[i][0])
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    tree_adj = [[] for _ in range(n)]
    in_tree = [False] * m
    total_w = 0
    used = 0

    for i in order:
        w, u, v = edges[i]
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            in_tree[i] = True
            tree_adj[u].append((v, w))
            tree_adj[v].append((u, w))
            total_w += w
            used += 1
            if used == n - 1:
                break

    LOG = max(2, n.bit_length() + 1)
    depth = [0] * n
    up = [[0] * n for _ in range(LOG)]
    mx = [[0] * n for _ in range(LOG)]

    visited = [False] * n
    root = 0
    visited[root] = True
    dq = deque([root])
    while dq:
        u = dq.popleft()
        for v, w in tree_adj[u]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                up[0][v] = u
                mx[0][v] = w
                dq.append(v)

    for k in range(1, LOG):
        for v in range(n):
            up[k][v] = up[k - 1][up[k - 1][v]]
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][up[k - 1][v]])

    def path_max(u, v):
        res = 0
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                res = max(res, mx[k][u])
                u = up[k][u]
        if u == v:
            return res
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                res = max(res, mx[k][u], mx[k][v])
                u = up[k][u]
                v = up[k][v]
        res = max(res, mx[0][u], mx[0][v])
        return res

    best_extra = None
    tie_found = False

    for i in range(m):
        if in_tree[i]:
            continue
        w, u, v = edges[i]
        pm = path_max(u, v)
        if w == pm:
            tie_found = True
            break
        candidate = total_w - pm + w
        if best_extra is None or candidate < best_extra:
            best_extra = candidate

    second = total_w if tie_found else best_extra

    print(total_w)
    print(second)


solve()

Step-by-Step 解説

1MSTの構築（Kruskal法）
辺を重み順にソートし、Union-Findでサイクルができない辺だけを採用する標準的なKruskal法で $W$ と木の隣接リストを得る。$O(M \log M)$。

2非木辺追加による閉路とカット性質
MSTに含まれない辺 $(u,v,w)$ を追加すると、木上の $u$-$v$ パスと合わせて唯一の閉路ができる。MSTのカット性質から、この閉路上でMSTに含まれる辺の重みは全て $w$ 以下であることが保証される。特に閉路上の最大辺重みが $w$ と等しい場合、その辺を入れ替えても総重みは変化しない別の全域木ができる。

3二分累乗によるパス最大値クエリ
各頂点についてBFSで根からの深さ・直上の親・親への辺重みを求めたあと、$2^k$ 個上の祖先とその区間の最大辺重みを二分累乗で前計算する。任意の2頂点間のLCAを求めながら、通過した区間の最大値を同時に更新することでパス上の最大辺重みを $O(\log N)$ で求められる。

4全非木辺を調べて答えを確定
各非木辺について path_max を求め、等しければ即座に $W_2=W$ で確定、大きければ候補 $W - \text{path\_max} + w$ を計算し全体の最小値を取る。全体 $O((N+M)\log N)$。

5なぜ「2番目に大きい辺」の管理が不要か
本問は「辺集合が異なればよい（重みは同じでもよい）」と定義したため、同重み置き換えが見つかった時点でそれが即座に最適解（$W$自体）となり、区間の「最大値と、それとは異なる値の2番目の最大値」の両方を管理する高度なテクニックが不要になる。

よくあるミス

ミス	原因	正しい書き方
非木辺の重みが path_max と等しい場合も候補計算に含めてしまう	カット性質・同重み置き換えの意味を理解していない	等しい場合は即座に $W_2=W$ で確定してよい
`up[k][v]` の初期化で根の親を根自身にしていない	根を超えるジャンプで範囲外参照になる	根の `up[0][root]=root`（自己ループ）、`mx[0][root]=0` とする
LOGの値を固定値にして大きい $N$ で不足する	$N$ に応じた可変長にしていない	`LOG = N.bit_length() + 1` のように動的に計算する
Kruskalで同じ重みの辺の処理順を気にしない	出力が一意に決まらないと誤解	本問は $W,W_2$ の値のみを問うのでタイブレークの違いは結果に影響しない

次のステップ

発展: 「MSTが一意かどうか」の判定問題は、本問の「等しい置き換えが1本でも見つかるか」の判定そのもの。
次回予告: 赤黒木（Red-Black Tree）への挿入操作と回転回数のカウント

自己評価

完全理解おおむね理解要復習

Day 125-Q4 — 次点全域木（Second Best Minimum Spanning Tree）

問題