Day 143-Q1 — Kruskal復元木（ボトルネック最短路のLCA帰着）

2026-09-04 赤色 Master / Phase 8+ ★★★★★★★★★ Kruskal法の併合履歴を二分木として保持し経路上の最大辺重み最小化をLCAに帰着

問題

$N$ 頂点 $M$ 辺の無向グラフが与えられる（連結とは限らない）。各辺には重み $w$ がある。

$Q$ 個のクエリ $(a,b)$ について、$a$ から $b$ へ至る経路のうち経路上の最大辺重みが最小となる値（ボトルネック最短路）を求めよ。同じ連結成分に属さない場合は -1 を出力する。

解法の骨子

  1. 辺を重みの昇順にソートし、Kruskal法と同様にUnion-Findで併合していく
  2. 各Union-Findの根に「対応する復元木のノード番号」を持たせる（初期状態は頂点自身が葉ノード）
  3. $u,v$ が異なる成分なら新しい内部ノード（値$=w$）を作り、併合前の2成分の根が指すノードを子にする
  4. 全辺処理後、各連結成分ごとに1本の二分木（値は根に近いほど大きい）ができる
  5. クエリ$(a,b)$の答えは、同じ木ならLCAの値、異なる木なら-1

入力形式

N M Q
u_1 v_1 w_1
:
u_M v_M w_M
a_1 b_1
:
a_Q b_Q

制約

$1 \le N \le 2\times10^5$
$0 \le M \le 2\times10^5$
$1 \le Q \le 2\times10^5$
$1 \le w_i \le 10^9$

入出力例

入力例1

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

出力例1

4
4

1-4: 経路1-2-3-4の最大辺重み4が最小（1-5-4だと5）。2-5: 経路2-3-4-5の最大辺重み4が最小。

概念図：Kruskal復元木

入力例1の復元木（根に近いほど値が大きい） 4 3 2 1 1 4 5 2 3 LCA(1,4)=根(値4) / LCA(2,5)=根(値4)

ヒント（段階的開示）

ヒント1（方向性）

「経路上の最大辺重みを最小化する」問題は、実は最小全域木上の一意なパスが最適であることが知られている（MST上のu-vパスの最大辺重みは、元グラフの全てのu-vパスの最大辺重みの最小値と一致する）。MSTを構築しつつその構築過程を木として記録すれば、任意のクエリに高速に答えられる。

ヒント2（アプローチ）

Kruskal法が異なる成分同士を繋ぐたびに、その「併合イベント」をノードとして木に記録する。$N$個の葉と最大$N-1$個の内部ノードからなる二分木ができ、内部ノードの値は根に近いほど大きい（辺重みが昇順に処理されるため）。2頂点のLCAに対応する併合イベントの値が、ボトルネック最短路の値になる。

ヒント3（誘導） 
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.node_id = list(range(n))

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

def build_reconstruction_tree(N, edges):
    edges.sort(key=lambda e: e[2])
    dsu = DSU(N)
    children = [[] for _ in range(2 * N)]
    value = [0] * (2 * N)
    next_node = N
    for u, v, w in edges:
        ru, rv = dsu.find(u), dsu.find(v)
        if ru == rv:
            continue
        new_node = next_node
        next_node += 1
        children[new_node] = [dsu.node_id[ru], dsu.node_id[rv]]
        value[new_node] = w
        dsu.parent[ru] = rv
        dsu.node_id[rv] = new_node
    return children, value, next_node

模範解答 (Python)

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1

    edges = []
    for _ in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        edges.append((u, v, w))

    queries = []
    for _ in range(Q):
        a = int(input_data[idx]) - 1; idx += 1
        b = int(input_data[idx]) - 1; idx += 1
        queries.append((a, b))

    max_nodes = 2 * N
    parent_dsu = list(range(N))
    node_id = list(range(N))

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

    children = [None] * max_nodes
    value = [0] * max_nodes
    tree_parent = [-1] * max_nodes
    next_node = N

    edges.sort(key=lambda e: e[2])
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        left, right = node_id[ru], node_id[rv]
        new_node = next_node
        next_node += 1
        children[new_node] = (left, right)
        value[new_node] = w
        tree_parent[left] = new_node
        tree_parent[right] = new_node
        parent_dsu[ru] = rv
        node_id[rv] = new_node

    total_nodes = next_node

    LOG = max(1, total_nodes.bit_length())
    up = [[-1] * total_nodes for _ in range(LOG)]
    depth = [0] * total_nodes
    visited = [False] * total_nodes

    roots = []
    for v in range(total_nodes):
        if tree_parent[v] == -1 and not visited[v] and (v < N or children[v] is not None):
            roots.append(v)

    for r in roots:
        stack = [r]
        visited[r] = True
        up[0][r] = -1
        while stack:
            node = stack.pop()
            ch = children[node]
            if ch:
                for c in ch:
                    if not visited[c]:
                        visited[c] = True
                        depth[c] = depth[node] + 1
                        up[0][c] = node
                        stack.append(c)

    for k in range(1, LOG):
        upk, upk1 = up[k], up[k - 1]
        for v in range(total_nodes):
            p = upk1[v]
            upk[v] = -1 if p == -1 else upk1[p]

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        diff = depth[a] - depth[b]
        for k in range(LOG):
            if (diff >> k) & 1:
                a = up[k][a]
        if a == b:
            return a
        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]
                b = up[k][b]
        return up[0][a]

    def find_root(v):
        while up[0][v] != -1:
            v = up[0][v]
        return v

    out = []
    for a, b in queries:
        if find_root(a) != find_root(b):
            out.append("-1")
        else:
            l = lca(a, b)
            out.append(str(value[l]))

    print("\n".join(out))

main()

Step-by-Step 解説

1MST上のパスがボトルネック最短路になる理由
「サイクル性質」の裏返しにより、MST上のa-bパスの最大辺重みが元グラフの全a-bパス中の最小ボトルネック値と一致する。
2復元木として併合イベントを記録
Union-Findの併合をノード生成として記録することでMST構築の履歴を二分木として保持。内部ノードの値は根に近づくほど大きい。
3LCAが答えになる理由
$a,b$が復元木上で初めて同じ部分木に入るのはLCAに対応する併合イベントの時点であり、その値が最小ボトルネック値。
4ダブリングによるLCA実装
$2N-1$個以下のノードに対し親配列のダブリングでO(log N)前処理・O(log N)クエリ。森を扱うため同じ木の根か事前確認が必要。
5計算量
構築O((N+M)log(N+M))、LCA前処理O(N log N)、各クエリO(log N)。

よくあるミス

ミス原因正しい書き方
復元木の内部ノード番号を頂点番号と混同する頂点0..N-1と内部ノードN..2N-2の添字がずれるnode_id[]配列でDSUの根が指す復元木ノードを明示管理
非連結グラフを考慮せず単一木としてLCAを取る元グラフが非連結だと復元木も森になるクエリ前に両頂点の木の根が同じか判定し異なれば-1
併合が発生しない辺でもノードを作ってしまうサイクルを作る辺をスキップし忘れるfind(u)==find(v)のときはノードを作らずスキップ
LCA前処理を再帰DFSで行いスタックオーバーフローNが大きいと木の高さがO(N)になり得るスタックを使った反復DFSで深さ・親を計算
内部ノードの値が根に近いほど大きいという前提を無検証で信じる辺をソートし忘れると前提が崩れる辺を重みの昇順に必ずソートしてから構築

次のステップ

  • 発展: クエリをオンラインにも対応させるため、Kruskal復元木ではなくLink-Cut Treeで同じ問題を解いてみよ。
  • 発展2: 経路上でk番目に大きい辺重みを求めるクエリに拡張し、復元木のオイラーツアー＋マージソート木でどう解けるか考察せよ。

自己評価

自分の回答

気づき・メモ