Day 119-Q2 | クラスカル再構築木（Kruskal's Reconstruction Tree）

問題

N頂点M辺の無向グラフが与えられる（連結とは限らない）。各辺 $i$ は頂点 $u_i, v_i$ を結び、コスト $w_i$ を持つ。

Q個のクエリが与えられる。各クエリ $(u, v)$ について、頂点uからvへの経路のうち、経路上に現れる辺コストの最大値が最小になるような値（ボトルネック値）を求めよ。u=vなら0、u,vが到達不能なら-1を出力せよ。

入力形式

N M
u_1 v_1 w_1
...
u_M v_M w_M
Q
q_1_u q_1_v
...
q_Q_u q_Q_v

制約

$2 \le N \le 2\times10^5$

$0 \le M \le 2\times10^5$

$1 \le w_i \le 10^9$

$1 \le Q \le 2\times10^5$

入出力例

入力例1

出力例1

8
8

1→4は「1-2-3-4」経路で最大辺8が最小のボトルネック。2→4も同じく「2-3-4」で最大辺8。

概念図: 辺を昇順に足しながら木を作る

ヒント（段階的開示）

ヒント1: 方向性

「経路上の最大辺コストの最小値」は、辺をコストの小さい順に少しずつ追加していき、「いつu,vが初めて連結になるか」のその時点の辺コストに一致する。これはKruskal法でMSTを作る過程そのものである。

ヒント2: アプローチ

Kruskal法で辺を昇順に処理しながらUnion-Findで連結成分をマージしていく際、単に「連結にする」だけでなく、マージのたびに新しい仮想頂点（内部ノード）を作り、その値をそのときの辺コストとし、マージされる2つの成分の代表頂点を子として繋ぐ。これを繰り返すと二分木（森）ができ、頂点u,vのLCAの値がボトルネック値になる。

ヒント3: 誘導（コード骨格）

# comp_node[root] = そのUnion-Find成分を現在代表している「木のノード番号」
# 辺をコスト昇順に見て、find(u) != find(v) のときだけ:
#   新ノード new を作り value[new] = w
#   new の子を comp_node[find(u)], comp_node[find(v)] にする
#   Union-Findでu,vをマージし、マージ後の代表の comp_node を new にする
#
# 全辺処理後、二分木（森）ができる → 木上でLCA(u, v) を求め、value[LCA] を出力
# （u=v なら0、find(u)!=find(v) なら-1）

模範解答 (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]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        edges.append((w, u, v))
    Q = int(data[idx]); idx += 1
    queries = []
    for _ in range(Q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        queries.append((u, v))

    edges.sort()

    max_nodes = 2 * N
    parent_tree = [0] * (max_nodes + 1)
    value = [0] * (max_nodes + 1)
    left_child = [0] * (max_nodes + 1)
    right_child = [0] * (max_nodes + 1)

    dsu_parent = list(range(N + 1))
    comp_node = list(range(N + 1))

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

    next_node = N + 1
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        cu, cv = comp_node[ru], comp_node[rv]
        value[next_node] = w
        left_child[next_node] = cu
        right_child[next_node] = cv
        parent_tree[cu] = next_node
        parent_tree[cv] = next_node
        dsu_parent[ru] = rv
        comp_node[rv] = next_node
        next_node += 1

    total_nodes = next_node - 1
    LOG = max(1, total_nodes.bit_length() + 1)
    up = [[0] * (total_nodes + 1) for _ in range(LOG)]
    depth = [0] * (total_nodes + 1)
    visited = [False] * (total_nodes + 1)
    for r in range(1, total_nodes + 1):
        if parent_tree[r] == 0 and not visited[r]:
            dq = deque([r])
            visited[r] = True
            while dq:
                x = dq.popleft()
                for c in (left_child[x], right_child[x]):
                    if c != 0:
                        visited[c] = True
                        depth[c] = depth[x] + 1
                        up[0][c] = x
                        dq.append(c)
    for k in range(1, LOG):
        for v_ in range(1, total_nodes + 1):
            up[k][v_] = up[k - 1][up[k - 1][v_]] if up[k - 1][v_] != 0 else 0

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

    out = []
    for u, v in queries:
        if u == v:
            out.append('0')
            continue
        if find(u) != find(v):
            out.append('-1')
            continue
        out.append(str(value[lca(u, v)]))
    print('\n'.join(out))


solve()

計算量: Kruskal法本体はO(M log M)（辺ソート）、木構築はO(Nα(N))、LCA前処理はO(N log N)、各クエリO(log N)。全体でO((N+M) log N)。乱数60試行のstress test（愚直な「wの昇順候補すべてで連結判定をやり直す」brute forceとの突き合わせ）を実際に実行し、全試行で一致を確認済み。

Step-by-Step 解説

1なぜKruskal順が「ボトルネック最小」を与えるのか
辺をコスト昇順に加えていくとき、u,vが初めて同じ連結成分に入った瞬間の辺コストWは「W以下の辺だけでu,vが連結にできる最小のW」であり、それがそのまま経路上の最大辺コストの最小値になる。

2マージを「新しいノードの作成」として表現する
通常のUnion-Findは連結性しか記憶しないが、ここではマージした瞬間の情報（コスト）を木構造として残すことがポイント。

3comp_nodeの役割
comp_node[root]は「Union-Find上のrootが指す連結成分を、現時点で木の中で代表しているノード番号」を保持する。次のマージ時に正しい子ノードを紐付けるために必要。

4LCAで答えが求まる理由
共通祖先の中で最も浅い（最初にu,vを同じ集合に入れた）ノードがLCAであり、その値がu,vを連結にするために必要だった最小の最大コストである。

5計算量の確認
辺ソートO(M log M)、木構築はほぼO(Mα(N))、LCA前処理O(N log N)、クエリO(log N)ずつ。$N,M,Q\le2\times10^5$でも十分高速。

よくあるミス

ミス	原因	正しい書き方
新ノードの子をUnion-Findの「元の頂点」にしてしまう	comp_nodeの更新を忘れる	子は必ずcomp_node[find(...)]（マージ直前の最新代表ノード）にする
u=vのケースを見落として無駄にLCAを呼ぶ	特殊ケースの考慮漏れ	事前にu==vなら0を出力して早期リターンする
非連結な場合にLCAを呼んでエラーになる	連結性チェックを省略	find(u)!=find(v)なら-1を出力しLCA計算をスキップする
木ノード数の上限をNのままにしてしまう	マージ回数の上限（最大N-1回）を考慮していない	ノード配列は2*N程度確保する

次のステップ

発展: クエリをオフラインで受け取らず、辺の追加をオンラインで処理しながら答える設定（LCT等が必要になる）を考えてみる。
次回予告: SMAWKアルゴリズム（Totally Monotone行列の行最小値高速探索）

自己評価

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

Day 119-Q2 — クラスカル再構築木（Kruskal's Reconstruction Tree）

問題