問題
$N$ 頂点の根付き木（根は頂点1）と $Q$ 個のクエリ。各クエリ $(u, v)$ について、$u$ と $v$ の LCA を求めよ。
制約
$1 \le N, Q \le 10^5$
木は連結
入出力例
入力例 1
7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
2 3出力例 1
2
1
1ヒント (段階的開示)
ヒント1: 方向性
ダブリング（Sparse Table）で LCA を $O(\log N)$ クエリで解く。
ヒント2: アプローチ
各頂点 $v$ について
parent[k][v] = $v$ の $2^k$ 個上の祖先を前計算。ヒント3: 誘導
for k in range(1, LOG):
for v in range(1, N + 1):
if parent[k-1][v] != -1:
parent[k][v] = parent[k-1][parent[k-1][v]]模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
LOG = 17
depth = [0] * (N + 1)
parent = [[-1] * (N + 1) for _ in range(LOG)]
visited = [False] * (N + 1)
q = deque([1])
visited[1] = True
while q:
v = q.popleft()
for u in graph[v]:
if not visited[u]:
visited[u] = True
depth[u] = depth[v] + 1
parent[0][u] = v
q.append(u)
for k in range(1, LOG):
for v in range(1, N + 1):
if parent[k-1][v] != -1:
parent[k][v] = parent[k-1][parent[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 = parent[k][u]
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if parent[k][u] != parent[k][v]:
u = parent[k][u]
v = parent[k][v]
return parent[0][u]
for _ in range(Q):
u, v = map(int, input().split())
print(lca(u, v))
solve()Step-by-Step 解説
1BFS で深さと直接親を記録
根 1 から BFS。
根 1 から BFS。
2ダブリングテーブル構築
parent[k][v] = parent[k-1][parent[k-1][v]]、$O(N \log N)$。
3LCA クエリ
深さを揃える → 「親が一致しないギリギリ」まで同時に上がり、その直接の親が LCA。
深さを揃える → 「親が一致しないギリギリ」まで同時に上がり、その直接の親が LCA。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 深さ揃え後の u==v 確認を忘れる | 一方が他方の祖先の場合に誤答 | if u == v: return u |
| LOG の値が不足 | $N=10^5$ には $2^{17}=131072$ が必要 | LOG = 17 |
次のステップ
- 発展問題: 2頂点間の距離クエリ
dist(u,v) = depth[u] + depth[v] - 2*depth[lca(u,v)]