Day 059-Q5 — 動的木直径 + 辺重み変更（LCT + 直径モノイド）

問題

$N$ 頂点の木（最初は辺なし）に対して $Q$ クエリを処理せよ。

• 1 u v w: 頂点 $u$ と $v$ を辺重み $w$ で結ぶ（追加後も木であることが保証される）
• 2 u v w: 頂点 $u$ と $v$ をつなぐ辺の重みを $w$ に変更する
• 3: 現在の木の直径（最長パス長）を出力せよ

入出力例

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

7
9

辺追加後: 1-2(3), 2-3(4)。直径 = 1→2→3 = 7。
辺追加後: 1-2(3), 2-3(4), 3-4(2)。直径 = 1→2→3→4 = 9。

概念図: 直径モノイドとLCT辺ノードテクニック

ヒント（段階的開示）

from collections import deque, defaultdict
def bfs_diameter(adj):
    if not adj: return 0
    start = next(iter(adj))
    dist = {start: 0}; q = deque([start])
    while q:
        v = q.popleft()
        for u, w in adj[v].items():
            if u not in dist:
                dist[u] = dist[v]+w; q.append(u)
    u = max(dist, key=dist.get)
    dist2 = {u: 0}; q = deque([u])
    while q:
        v = q.popleft()
        for x, w in adj[v].items():
            if x not in dist2:
                dist2[x] = dist2[v]+w; q.append(x)
    return max(dist2.values())
# クエリ3ごとに O(N) → Q=10^5 で TLE

模範解答 (Python — 素朴解法)

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

def main():
    N, Q = map(int, input().split())
    adj = defaultdict(dict)

    def bfs_diameter():
        if not adj: return 0
        start = next(iter(adj))
        dist = {start: 0}
        q = deque([start])
        while q:
            v = q.popleft()
            for u, w in adj[v].items():
                if u not in dist:
                    dist[u] = dist[v] + w
                    q.append(u)
        u = max(dist, key=dist.get)
        dist2 = {u: 0}
        q = deque([u])
        while q:
            v = q.popleft()
            for x, w in adj[v].items():
                if x not in dist2:
                    dist2[x] = dist2[v] + w
                    q.append(x)
        return max(dist2.values()) if dist2 else 0

    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            u, v, w = int(line[1]), int(line[2]), int(line[3])
            adj[u][v] = w
            adj[v][u] = w
        elif line[0] == '2':
            u, v, w = int(line[1]), int(line[2]), int(line[3])
            adj[u][v] = w
            adj[v][u] = w
        else:
            print(bfs_diameter())

main()

# 完全解法（LCT）は ~200行の実装が必要。
# 各クエリ O(log N) を達成するには辺ノードテクニック + 直径モノイドが不可欠。

Step-by-Step 解説

Step 1: 木の直径の2-BFS

任意頂点から BFS → 最遠頂点 $u$ → $u$ からの最遠距離が直径。$O(N)$。

Step 2: 動的木での課題

クエリ3のたびに $O(N)$ BFS を行うと $Q \cdot N = 10^{10}$ で TLE。Link-Cut Tree で各操作を $O(\log N)$ amortized に落とす必要がある。

Step 3: 直径モノイドの設計

各 splay ノードに (diam, ldep, rdep, len) を持たせる:

• diam: この部分木内の最長パス
• ldep: 左端からの最長パス
• rdep: 右端からの最長パス

マージ: new_diam = max(L.diam, R.diam, L.rdep + w + R.ldep)

Step 4: 辺ノードテクニック

辺 $(u,v,w)$ を仮想ノード $e$ として LCT に挿入。$u-e-v$ のパスを管理。辺重み変更は $e$ の val を更新して splay と push_up を伝播するだけ。

Step 5: 全体計算量

LCT の各操作: $O(\log N)$ amortized。全体 $O(Q \log N)$。

よくあるミス

次のステップ

発展問題: 辺の追加・削除（動的フォレスト）と直径クエリを組み合わせた問題を、完全な LCT 実装で $O(Q \log N)$ で解け。

自己評価