Day 099-Q3 — MST検証アルゴリズム（全方位木DPによる最大辺クエリ）

2026-07-22 赤色 Master / Phase 8+ ★★★★★★★★★ MST Verification / Cycle Property

問題

$N$ 頂点 $M$ 辺の連結な無向重み付きグラフと、$N-1$ 本の辺からなる「候補となる全域木」が与えられる。この候補の全域木が 最小全域木（MST） かどうかを判定せよ。

サイクル性質（Cycle Property）: 全域木に含まれない各辺 $(u,v,w)$ について、木上の $u$–$v$ パス上の最大辺重みが $w$ 以下であれば、その辺で木を改善することはできない。すべての非木辺でこれが成り立つとき、かつそのときに限り、候補はMSTである。パス最大値は LCAダブリングに「経路上の最大辺重み」を同時に持たせることで $O(\log N)$ で求められる（理論上は Komlós のアルゴリズムで $O(N+M)$ も可能）。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M
i_1 i_2 ... i_{N-1}

最後の行は、全域木として選ばれている辺の番号（1-indexed）を $N-1$ 個。

制約

$2 \le N \le 2\times10^5$
$N-1 \le M \le 2\times10^5$
$1 \le w_i \le 10^9$
グラフは連結、与えられる木は正当

入出力例

入力例1

4 5
1 2 1
2 3 2
3 4 1
1 3 3
2 4 4
1 2 3

出力例1

Yes

入力例2

4 5
1 2 1
2 3 2
3 4 1
1 3 3
2 4 4
1 4 5

出力例2

No

概念図

候補木 + 非木辺のサイクル性質チェック 1 2 3 4 w=1 w=2 w=1 非木辺 (2,4,w=4)：木上パス2-3-4の最大辺=2 ≤ 4 → OK 非木辺 (1,3,w=3)：木上パス1-2-3の最大辺=2 ≤ 3 → OK → すべての非木辺でサイクル性質を満たす ⇒ この候補木はMST（Yes）

ヒント（段階的開示）

ヒント1: 方向性
候補木がMSTかどうかを判定するのに、必ずしも真のMSTを別途構築して重みを比較する必要はない。木に含まれない辺それぞれについて「その辺を使うと木が改善できるか」だけを個別にチェックする方法を考えよ。
ヒント2: アプローチ
非木辺 $(u,v,w)$ を木に追加すると閉路ができる。閉路中の最大辺を除去すれば重みは非増加になるはずなので、「$w$ が木上の $u$–$v$ パスの最大辺重み以上」であることがすべての非木辺で成り立てば、木は改善不可能=MSTである。パス最大値クエリはLCAダブリングのテーブルに「そこまでの経路の最大辺重み」も一緒に持たせれば同時に求められる。
ヒント3: 誘導（コード骨格） 
LOG = 18
up = [[-1] * n for _ in range(LOG)]
maxedge = [[0] * n for _ in range(LOG)]
for k in range(1, LOG):
    for v in range(n):
        p = up[k - 1][v]
        if p == -1:
            continue
        up[k][v] = up[k - 1][p]
        maxedge[k][v] = max(maxedge[k - 1][v], maxedge[k - 1][p])

def path_max(u, v):
    # depth[u]>=depth[v]にswapし、深さを揃えながらmaxedgeを取り
    # LCAまで登る
    ...

各非木辺 $(u,v,w)$ について path_max(u,v) <= w を確認し、1つでも破れば No。

模範解答 (Python)

import sys
from collections import deque


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

    edges = []
    for _ 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((u, v, w))

    tree_idx = [int(data[idx + i]) - 1 for i in range(n - 1)]
    idx += n - 1
    tree_edge_set = set(tree_idx)

    adj = [[] for _ in range(n)]
    for ti in tree_idx:
        u, v, w = edges[ti]
        adj[u].append((v, w))
        adj[v].append((u, w))

    LOG = 1
    while (1 << LOG) < n:
        LOG += 1
    LOG += 1

    depth = [-1] * n
    up = [[-1] * n for _ in range(LOG)]
    maxedge = [[0] * n for _ in range(LOG)]

    depth[0] = 0
    dq = deque([0])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if depth[v] == -1:
                depth[v] = depth[u] + 1
                up[0][v] = u
                maxedge[0][v] = w
                dq.append(v)

    for k in range(1, LOG):
        upk, upk1 = up[k], up[k - 1]
        mek, mek1 = maxedge[k], maxedge[k - 1]
        for v in range(n):
            p = upk1[v]
            if p == -1:
                continue
            upk[v] = upk1[p]
            mek[v] = max(mek1[v], mek1[p])

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

    ok = True
    for i, (u, v, w) in enumerate(edges):
        if i in tree_edge_set:
            continue
        if path_max(u, v) > w:
            ok = False
            break

    print("Yes" if ok else "No")


solve()
計算量: 前処理 $O(N\log N)$、各クエリ $O(\log N)$、全体 $O((N+M)\log N)$。

Step-by-Step 解説

1候補木の隣接リスト構築
入力で指定された$N-1$本の辺だけを使って木を作る。
2BFSで深さと直近の親を求める
頂点0を根としてBFSし、depth,up[0],maxedge[0]を求める。
3ダブリングテーブルの構築
up[k][v]と同時にmaxedge[k][v]（$2^k$個上まで登る経路上の最大辺重み）を求める。
4path_maxクエリ
深さを揃えながら登り、LCAの1つ手前まで同時に登って最大値を反映する。$O(\log N)$。
5非木辺のサイクル性質チェック
すべての非木辺でpath_max(u,v) <= wを確認。1本でも破ればNo。

よくあるミス

ミス原因正しい書き方
総重み比較だけでMST判定サイクル性質による個別チェックの本質を学べない各非木辺についてパス最大値をダブリングで確認する
深さを揃える過程でmaxedgeの反映を忘れる通過した辺の重みを見落とす揃えるループ内でもbest=max(best,maxedge[k][u])を行う
u==vになった直後の処理を省略深さを揃えた時点でLCAが片方の祖先だった場合を見逃すif u==v: return bestの早期リターンを入れる
LOGの大きさが不足$2^{LOG}<N$だと祖先探索が不完全になる$LOG$は$\lceil\log_2 N\rceil+1$程度余裕を持たせる

次のステップ

  • 発展: Kruskal Reconstruction Treeを使うとパス最大値クエリが$O(1)$（前処理$O((N+M)\alpha(N))$）に高速化できる
  • 次回予告: Batcherのビトニックソートネットワーク（Sorting Network・比較器構成）

自己評価

自分の回答

気づき・メモ