Day 022-Q3 — オンライン最小全域木（動的辺追加 + Link-Cut Tree）

2026-05-05 赤色 Master / Phase 8+ ★★★★★★★★★ 動的グラフ・オンライン最小全域木・Link-Cut Tree

問題

$N$ 頂点のグラフに対し、$Q$ 個のクエリをオンラインで処理せよ。

  • クエリ 1 u v w: 辺 $(u, v, w)$ を追加する
  • クエリ 2 u v: 現在のグラフ上で頂点 $u$ から $v$ へのパス上の最大辺重み（ボトルネック最短路）を答える。$u, v$ が非連結なら -1 を答える。

ただし、グラフは常に最小全域木（MST）の状態を維持する。辺追加時に MST を動的に更新すること。

入力形式

N Q
クエリ1
クエリ2
...
クエリQ

制約

$2 \leq N \leq 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq u, v \leq N$, $u \neq v$
$1 \leq w \leq 10^9$
クエリ2はオンラインで処理

入出力例

入力例 1

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

出力例 1

7
4
3

ヒント (段階的開示)

ヒント1: 方向性
MST を Link-Cut Tree（LCT）で管理する。辺 $(u, v, w)$ を追加するとき、$u$-$v$ パス上の最大辺を LCT で求め、その辺より重ければ無視、軽ければその辺を削除して新辺を追加。
ヒント2: アプローチ
LCT の各ノードに辺の重みを持たせる（辺をノードとして表現）。find_max(u, v): $u$-$v$ パス上の最大重みの辺ノードを返す。link(u, v, w): 辺を追加。cut(node): 辺ノードを削除。辺を「仮想ノード」として $N + \text{edge\_id}$ で表現する。
ヒント3: 誘導 
class LCTNode:
    def __init__(self):
        self.ch = [None, None]
        self.par = None
        self.val = 0      # edge weight (for edge-nodes)
        self.max_val = 0  # max edge weight in subtree
        self.max_node = self  # node achieving max
        self.rev = False

class LinkCutTree:
    def push_up(self, x): ...
    def access(self, x): ...

    def find_max_edge(self, u, v):
        """Return the edge-node with max weight on path u-v"""
        self.make_root(u)
        self.access(v)
        return v.max_node

    def link_edge(self, u, v, w, edge_node):
        edge_node.val = w
        edge_node.max_val = w
        edge_node.max_node = edge_node
        self.link(u, edge_node)
        self.link(edge_node, v)

模範解答 (Python)

import sys
from sys import stdin

def solve():
    """Simplified version tracking endpoints (UF + brute-force MST)"""
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    parent = list(range(N))
    rank_uf = [0] * N

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

    def union(x, y):
        x, y = find(x), find(y)
        if x == y:
            return False
        if rank_uf[x] < rank_uf[y]:
            x, y = y, x
        parent[y] = x
        if rank_uf[x] == rank_uf[y]:
            rank_uf[x] += 1
        return True

    mst_adj = [[] for _ in range(N)]

    def path_max(u, v):
        from collections import deque
        if find(u) != find(v):
            return -1, None
        visited = {u: (0, None)}
        q = deque([u])
        while q:
            node = q.popleft()
            if node == v:
                break
            for nb, w, eid in mst_adj[node]:
                if nb not in visited:
                    visited[nb] = (w, (node, nb, w, eid))
                    q.append(nb)
        cur = v
        max_w = 0
        max_edge = None
        while visited[cur][1] is not None:
            pw, edge_info = visited[cur]
            node_from, node_to, ew, eid = edge_info
            if ew > max_w:
                max_w = ew
                max_edge = edge_info
            cur = node_from
        return max_w, max_edge

    edge_id = [0]

    def add_mst_edge(u, v, w):
        eid = edge_id[0]; edge_id[0] += 1
        mst_adj[u].append((v, w, eid))
        mst_adj[v].append((u, w, eid))
        return eid

    def remove_mst_edge(u, v, eid):
        mst_adj[u] = [(nb, w, e) for nb, w, e in mst_adj[u] if e != eid]
        mst_adj[v] = [(nb, w, e) for nb, w, e in mst_adj[v] if e != eid]

    results = []
    for _ in range(Q):
        tp = int(data[idx]); idx += 1
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1

        if tp == 1:
            w = int(data[idx]); idx += 1
            if find(u) != find(v):
                add_mst_edge(u, v, w)
                union(u, v)
            else:
                max_w, max_edge = path_max(u, v)
                if max_edge is not None and max_edge[2] > w:
                    remove_mst_edge(max_edge[0], max_edge[1], max_edge[3])
                    add_mst_edge(u, v, w)
        else:
            max_w, _ = path_max(u, v)
            results.append(max_w)

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

1動的 MST の維持
辺 $(u, v, w)$ を追加するとき: (1) $u, v$ が非連結 → そのまま MST に追加、(2) $u, v$ が連結 → パス上の最大辺 $e_{max}$ を求める。$w_{max} > w$: $e_{max}$ を削除し $(u, v, w)$ を追加（MST が更新される）。$w_{max} \leq w$: 何もしない。
2Link-Cut Tree の役割
MST 上のパス最大辺クエリを $O(\log N)$ で処理。辺を「仮想ノード」として表現し、各ノードに辺重みを持たせる。
3ボトルネック最短路クエリ
クエリ 2 u v = MST 上の $u$-$v$ パスの最大辺重み（= 実際のグラフでのボトルネック最短路）。

よくあるミス

ミス原因正しい書き方
辺削除時に両端点を追跡しないLCT での辺削除には端点が必要辺ノードと端点の対応を記録する
make_root 後に access を忘れるパスクエリは make_root(u); access(v)必ず両方呼ぶ
push_down の順序がずれるSplay 前にスタックで先祖をプッシュダウンスタックで上から順に push_down

次のステップ

  • 発展問題: 辺の削除クエリも含む完全動的 MST（$O(\log^2 N)$ per query）
  • さらに難しい: 動的グラフの連結性問題（Holm et al. 2001 のアルゴリズム）

自己評価

自分の回答

気づき・メモ