Day 006-Q3 | 木の直径・LCA

問題

$N$ 頂点の重み付き木が与えられます。以下の2つを求めてください。

木の直径（最も遠い2頂点間の距離）
$Q$ 個のクエリ: 頂点 $u$ と頂点 $v$ の LCA（最小共通祖先）を出力

入力形式

N
a1 b1 w1
...（N-1 本の辺）
Q
u1 v1
...

制約

$2 \le N \le 10^5$

$1 \le Q \le 10^5$

$1 \le a_i, b_i \le N$

$1 \le w_i \le 10^9$

入出力例

入力例 1

出力例 1

9
1
3

ヒント (段階的開示)

ヒント1: 方向性

木の直径は「BFS/DFS を2回」で求められます。LCAはダブリング（二分祖先）で効率化します。

ヒント2: アプローチ

直径: 任意の頂点から BFS → 最遠頂点 $u$、$u$ から BFS → 最遠頂点 $v$、$u$-$v$ 間の距離が直径。
LCA（ダブリング）: anc[k][v] = 頂点 $v$ の $2^k$ 代前の祖先。深さを合わせてから同時に $2^k$ ずつ上に登る。

ヒント3: 誘導

LOG = 17  # 2^17 = 131072 > 10^5
# BFS で深さと親を計算
# ダブリング: anc[k][v] = anc[k-1][anc[k-1][v]]

模範解答 (Python)

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

def main():
    N = int(input())
    graph = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))
        graph[b].append((a, w))

    LOG = 17

    def bfs(root):
        depth = [-1] * (N + 1)
        dist = [0] * (N + 1)
        depth[root] = 0
        q = deque([root])
        while q:
            v = q.popleft()
            for u, w in graph[v]:
                if depth[u] == -1:
                    depth[u] = depth[v] + 1
                    dist[u] = dist[v] + w
                    q.append(u)
        return depth, dist

    # 木の直径
    _, dist1 = bfs(1)
    far1 = max(range(1, N + 1), key=lambda x: dist1[x])
    _, dist2 = bfs(far1)
    diameter = max(dist2[1:N+1])
    print(diameter)

    # LCA（ダブリング）
    depth, _ = bfs(1)
    anc = [[-1] * (N + 1) for _ in range(LOG)]

    for v in range(1, N + 1):
        for u, _ in graph[v]:
            if depth[u] == depth[v] - 1:
                anc[0][v] = u
    anc[0][1] = 1

    for k in range(1, LOG):
        for v in range(1, N + 1):
            if anc[k-1][v] != -1:
                anc[k][v] = anc[k-1][anc[k-1][v]]

    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 = anc[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if anc[k][u] != anc[k][v]:
                u = anc[k][u]
                v = anc[k][v]
        return anc[0][u]

    Q = int(input())
    for _ in range(Q):
        u, v = map(int, input().split())
        print(lca(u, v))

main()

Step-by-Step 解説

1木の直径（BFS 2回）
任意の頂点から最遠の点 $u$ を探す（BFS 1回目）。$u$ からの最遠距離が直径（BFS 2回目）。

2LCA ダブリングの前計算
anc[0][v] = 親ノード、anc[k][v] = anc[k-1][anc[k-1][v]]（$2^k$ 代前 = $2^{k-1}$ 代前の $2^{k-1}$ 代前）。

3LCA クエリ
深さを揃える → 同じ深さから同時に上がり、最初に一致する祖先を返す。

よくあるミス

ミス	原因	正しい書き方
直径を DFS 1回で求めようとする	間違い。2回必要	BFS/DFS を2回実行する
根の親を設定しない	無限ループになる	`anc[0][root] = root`
深さを揃えた後の処理を間違える	u == v のケースを忘れる	`if u == v: return u`

次のステップ

発展問題: LCA を使ったクエリ（2頂点間の距離を複数回求める）

自己評価

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

Day 006-Q3 — 木の直径・LCA

問題