Day 061-Q1 | Kruskal Reconstruction Tree（クラスカル再構成木）

問題

$N$ 頂点 $M$ 辺の重み付き無向グラフ $G$ が与えられる。辺 $i$ は頂点 $u_i, v_i$ を結び重みは $w_i$ である。

以下の $Q$ 個のクエリに答えよ：

クエリ型: ask s t x

頂点 $s$ から頂点 $t$ へ向かうパスのうち、最大辺重みが最小となるパスを選んだとき、その最大辺重みが $x$ 以下であるかを判定せよ。さらに、$x$ 以下の辺のみを使って到達可能な $s$ の連結成分に属する頂点数を出力せよ。到達できない場合は No を出力せよ。

制約

パラメータ	範囲
$N$	$2 \le N \le 10^5$
$M$	$1 \le M \le 2 \times 10^5$
$w_i$	$1 \le w_i \le 10^9$
$Q$	$1 \le Q \le 2 \times 10^5$
$s, t$	$1 \le s, t \le N,\; s \ne t$
$x$	$1 \le x \le 10^9$

入出力例

入力例 1

出力例 1

4
No
No

ask 1 4 5: 辺重み≤5 で{1,2,3,4}が連結 → 4頂点。ask 1 4 3: 辺3以下では1-2(3),3-4(2)のみ、1と4は非連結 → No。ask 1 5 5: 辺5以下では4-5(8)が使えず5に到達不可 → No。

概念図: Kruskal Reconstruction Tree

ヒント（段階的開示）

ヒント1: 方向性

最小ボトルネックパス問題は最小全域木（MST）と本質的に同値。Kruskal 再構成木は Kruskal のアルゴリズムを走らせながら、2つの連結成分を結合するたびに新しい内部ノードを作り、その重みをその辺の重みとする木。

ヒント2: アプローチ

再構成木の葉 = 元グラフの頂点（N個）
内部ノード = Kruskal でマージされた辺（最大 N-1 個）、重み = その辺の重み
最小ボトルネック s-t 間 = weight[lca(s, t)]
辺重み ≤ x での s の連結成分サイズ = 再構成木で s から上に辿りながら weight ≤ x が成り立つ最高祖先の leaf_count

ヒント3: コード骨格

# 辺を軽い順にソート
edges = sorted(edges, key=lambda e: e[2])
node_id = N  # 内部ノードID (N〜2N-2)
weight = [0] * (2*N)
leaf_count = [1] * (2*N)  # 元頂点は1, 内部ノードは合算

for w, u, v in edges:
    ru, rv = find(u), find(v)
    if ru != rv:
        weight[node_id] = w
        leaf_count[node_id] = leaf_count[cr_u] + leaf_count[cr_v]
        # node_id の子を cr_u, cr_v に設定し Union-Find を更新
        node_id += 1

# クエリ: LCA を求め weight[lca(s,t)] vs x を比較

模範解答 (Python)

import sys
from math import log2
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        edges.append((w, u, v))
    edges.sort()

    total = 2 * N
    parent_arr = list(range(total))
    rank_arr = [0] * total

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

    def unite(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return
        if rank_arr[rx] < rank_arr[ry]: rx, ry = ry, rx
        parent_arr[ry] = rx
        if rank_arr[rx] == rank_arr[ry]: rank_arr[rx] += 1

    weight = [0] * total
    leaf_count = [1] * total
    children = [[] for _ in range(total)]
    tree_parent = [-1] * total
    comp_root = list(range(N))
    node_id = N

    for w, u, v in edges:
        ru = find(u); rv = find(v)
        if ru == rv: continue
        nid = node_id
        weight[nid] = w
        cr_u = comp_root[ru]; cr_v = comp_root[rv]
        children[nid] = [cr_u, cr_v]
        tree_parent[cr_u] = nid; tree_parent[cr_v] = nid
        leaf_count[nid] = leaf_count[cr_u] + leaf_count[cr_v]
        unite(nid, ru); unite(nid, rv)
        comp_root[find(nid)] = nid
        node_id += 1

    root = node_id - 1
    LOG = max(1, int(log2(node_id)) + 1)
    up = [[-1] * node_id for _ in range(LOG)]
    up[0] = tree_parent[:]
    up[0][root] = root

    from collections import deque
    depth = [0] * node_id
    visited = [False] * node_id
    q = deque([root]); visited[root] = True
    while q:
        v = q.popleft()
        for c in children[v]:
            if not visited[c]:
                visited[c] = True
                depth[c] = depth[v] + 1
                q.append(c)

    for k in range(1, LOG):
        for v in range(node_id):
            p = up[k-1][v]
            if p != -1: up[k][v] = up[k-1][p]

    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]

    Q = int(input())
    out = []
    for _ in range(Q):
        s, t, x = map(int, input().split())
        s -= 1; t -= 1
        l = lca(s, t)
        if weight[l] > x:
            out.append("No")
        else:
            node = s
            for k in range(LOG-1, -1, -1):
                p = up[k][node]
                if p != -1 and weight[p] <= x:
                    node = p
            out.append(str(leaf_count[node]))
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: 再構成木の構築

Kruskal で辺を軽い順に追加。2連結成分をマージするたびに内部ノード node_id を作り、weight と子を設定。元頂点 N 個 + 内部ノード最大 N-1 個で合計 2N-1 ノードの木が完成する。

Step 2: LCA = 最小ボトルネック

$s$-$t$ 間の最小ボトルネックは weight[lca(s, t)] に等しい。これは再構成木の本質的な性質。Binary Lifting で LCA を $O(\log N)$ で求める。

Step 3: 連結成分サイズ

閾値 $x$ での $s$ の連結成分 = 再構成木で $s$ から根方向に weight[p] ≤ x が成り立つ最高の祖先 $p$ の leaf_count[p]。Binary Lifting で $O(\log N)$。

よくあるミス

ミス	原因	正しい書き方
内部ノードIDが元頂点と衝突	node_id を 0 から始める	node_id = N からスタート
comp_root の更新が遅れる	unite 後に find が旧代表元を返す	unite 後に `comp_root[find(nid)] = nid`
グラフ非連結でクラッシュ	root = node_id - 1 が唯一の根でない	各クエリでそれぞれの連結成分を確認

次のステップ

発展問題: オンライン辺追加 + ボトルネッククエリ（Link-Cut Tree による動的版）
関連: Offline Dynamic Connectivity・重み付き Union-Find との比較

自己評価

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