Day 040-Q4 — 動的木直径（Union-Find + 直径端点管理）

2026-05-23 赤色 Master / Phase 8+ ★★★★★★★★★ Dynamic Tree Diameter

問題

$N$ 頂点の森（初期は孤立点）に対して $Q$ クエリを処理せよ。

  • クエリ1: 1 u v w — 辺 $(u,v)$ を重み $w$ で追加（異なる成分間のみ）
  • クエリ2: 2 t — 頂点 $t$ が属する木の直径を出力

制約

$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le w \le 10^9$
時間制限: 4sec / メモリ: 512MB

入出力例

入力例 1

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

出力例 1

8
8

概念図: 木の合体と直径更新

Tree A: 直径=3, 端点(1,2) 1 2 w=3 Tree B: 直径=5, 端点(2,3) 2 3 w=5 → 合体後: 直径=8, 端点(1,3) 1 2 3 3 5 直径候補の列挙（4 端点ペア + 各木の既存直径） 1. Tree A の直径: d=3 (端点 1,2) 2. Tree B の直径: d=5 (端点 2,3) 3. dist(a1=1, a2=2) = 3, dist(a1=1, b2=3) = 8 ← 最大！ 4. dist(b1=2, a2=2) = 0, dist(b1=2, b2=3) = 5 → 新直径 = max(3, 5, 3, 8, 0, 5) = 8 端点 (1, 3) を記録して次の合体クエリに備える

ヒント（段階的開示）

ヒント1: 方向性
Union-Find で各連結成分の「直径の両端点」を管理し、合体時に 4 通りの端点ペア距離を計算して最大を選ぶ。2 点間距離は BFS で計算。
ヒント2: 直径更新の法則
2本の木を辺でつなぐと新しい直径 = max(旧直径1, 旧直径2, 木1の端点aから木2の端点aへの距離, ...) の最大。木1の端点 (a1,b1)、木2の端点 (a2,b2) の 4 組み合わせを全試行。
ヒント3: 実装骨格 
# dia[root] = (diameter, endpoint_a, endpoint_b)
def union(u, v, w_edge):
    ru, rv = find(u), find(v)
    du, au, bu = dia[ru]
    dv, av, bv = dia[rv]
    adj[u].append((v, w_edge)); adj[v].append((u, w_edge))
    candidates = [(du, au, bu), (dv, av, bv)]
    for a in [au, bu]:
        for b in [av, bv]:
            d = bfs_dist(a, b)
            candidates.append((d, a, b))
    best = max(candidates, key=lambda x: x[0])
    # Union-Find 合体
    dia[new_root] = best

模範解答 (Python)

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())

    parent = list(range(N+1))
    rank_uf = [0] * (N+1)
    dia = [(0, i, i) for i in range(N+1)]
    adj = defaultdict(list)

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

    def bfs_dist(s, t):
        if s == t: return 0
        dist = {s: 0}
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for w, wt in adj[v]:
                if w not in dist:
                    dist[w] = dist[v] + wt
                    if w == t: return dist[w]
                    dq.append(w)
        return 0

    def union(u, v, w_edge):
        ru, rv = find(u), find(v)
        if ru == rv: return

        du, au, bu = dia[ru]
        dv, av, bv = dia[rv]

        adj[u].append((v, w_edge))
        adj[v].append((u, w_edge))

        candidates = [(du, au, bu), (dv, av, bv)]
        for a in [au, bu]:
            for b in [av, bv]:
                d = bfs_dist(a, b)
                candidates.append((d, a, b))

        best = max(candidates, key=lambda x: x[0])

        if rank_uf[ru] < rank_uf[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        if rank_uf[ru] == rank_uf[rv]:
            rank_uf[ru] += 1
        dia[ru] = best

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, u, v, w = line
            union(u, v, w)
        else:
            _, t = line
            rt = find(t)
            out.append(dia[rt][0])

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

solve()

Step-by-Step 解説

1直径の性質
木の直径は「最遠 2 頂点間のパス長」。2 本の木を辺でつなぐと新しい直径は旧直径 1、旧直径 2、または「木 1 の直径端点から木 2 の直径端点へのパス」のいずれかが最大。
2Union-Find 拡張
各連結成分の根に (diameter, endpoint_a, endpoint_b) を記録。Union 時に 4 通りの端点ペア距離を計算して最大を選ぶ。
32 点間距離の BFS
動的グラフなので adjacency list に辺を追加しながら BFS で距離計算。木なので BFS は O(N)。
4クエリ処理
クエリ 2 では find(t) で根を取得し、dia[root][0] を返す。
5計算量
簡単な実装では O(QN)。実際の競プロでは LCT を使って O(Q log N) にする。

計算量

union 1 回: $O(N)$（BFS 4 回）
query 1 回: $O(\alpha(N))$（Union-Find）
全体: $O(QN)$ — LCT を使うと $O(Q \log N)$
メモリ: $O(N + M)$

よくあるミス

ミス原因正しい書き方
直径候補 4 通りを見落とす(a1,b2) と (b1,a2) の計算忘れ4 ペア全候補を確認
辺追加前に dist 計算木がつながっていない辺を adj に追加してから BFS
Union-Find の rank/size を直径 info で上書きdia と uf を別配列で管理dia[ru] と rank_uf[ru] を分離
BFS で連結でない場合異なる成分への距離クエリ直径端点は同一成分内を保証

次のステップ

  • 発展: Link-Cut Tree での O(log N) 動的直径管理
  • 応用: 辺削除ありの動的直径（Offline + Undo DSU）
  • 類題: 森の直径クエリ（複数成分の最大直径）

自己評価