問題
$N$ 頂点の根付き木（根は頂点 $1$）が与えられる。各辺には重み $w_i$ がある。$Q$ 個のクエリ $(u_i, v_i)$ が与えられ、各クエリで頂点 $u_i$ と $v_i$ の間の距離（辺重みの和）を答えよ。
距離は $\text{dist}(u, v) = \text{dep}[u] + \text{dep}[v] - 2 \cdot \text{dep}[\text{lca}(u,v)]$ で求められる（$\text{dep}[v]$ は根から $v$ への辺重みの和）。Tarjan のオフライン LCA アルゴリズムを用いて全クエリを $O((N + Q) \alpha(N))$ で処理せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $\le 2 \times 10^5$ | 頂点数 |
| $Q$ | $\le 2 \times 10^5$ | クエリ数 |
| $w_i$ | $0 \le w_i \le 10^9$ | 辺重み |
入出力例
入力例1
5 3
1 2 3
1 3 5
2 4 2
2 5 4
4 5
3 4
1 5出力例1
6
10
9概念図: Tarjan の Offline LCA アルゴリズム
ヒント
ヒント1（方向性）
距離クエリは LCA を使えば $\text{dist}(u,v) = \text{dep}[u] + \text{dep}[v] - 2 \cdot \text{dep}[\text{lca}(u,v)]$ で計算できる。Binary Lifting を使ったオンライン LCA は $O(N \log N)$ 前処理・$O(\log N)$ クエリだが、Tarjan のオフラインアルゴリズムなら全クエリを DFS 中に $O((N+Q)\alpha(N))$ で処理できる。
ヒント2（アプローチ）
Tarjan の LCA アルゴリズムの手順：(1) DFS で頂点を訪問し $\text{dep}[v]$ を計算 (2) 頂点 $v$ の DFS が終わったら Union-Find で $v$ を親にマージし「訪問済み」にマーク (3) クエリ $(v, u)$ で $u$ が既に訪問済みなら $\text{lca}(v, u) = \text{ancestor}[\text{find}(u)]$
ヒント3（ほぼ答え）
def tarjan():
# DFS 終了時に Union-Find でマージ
# ancestor[find(v)] = v で代表頂点を管理
stk = [(v, par, False)]
while stk:
v, par, leaving = stk.pop()
if leaving:
visited[v] = True
for u, qi in queries[v]:
if visited[u]:
lca_res[qi] = ancestor[find(u)]
if par != -1:
union(v, par)
ancestor[find(par)] = par
else:
stk.append((v, par, True))
for u, w in graph[v]:
if u != par:
stk.append((u, v, False))模範解答
import sys
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, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
qs = []
queries = [[] for _ in range(N + 1)]
for i in range(Q):
u, v = map(int, input().split())
qs.append((u, v))
queries[u].append((v, i))
if u != v:
queries[v].append((u, i))
parent = list(range(N + 1))
ancestor = list(range(N + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
dep = [0] * (N + 1)
visited = [False] * (N + 1)
lca_res = [-1] * Q
stk = [(1, -1, False)]
while stk:
v, par, leaving = stk.pop()
if leaving:
visited[v] = True
for u, qi in queries[v]:
if visited[u]:
lca_res[qi] = ancestor[find(u)]
if par != -1:
pv, pp = find(v), find(par)
if pv != pp:
parent[pv] = pp
ancestor[find(par)] = par
else:
stk.append((v, par, True))
for u, w in graph[v]:
if u != par:
dep[u] = dep[v] + w
stk.append((u, v, False))
out = []
for i, (u, v) in enumerate(qs):
l = lca_res[i]
out.append(dep[u] + dep[v] - 2 * dep[l])
print('\n'.join(map(str, out)))
solve()Step-by-Step 解説
Step 1: 距離クエリと LCA の関係
| 項目 | 意味 |
|---|---|
| $\text{dep}[v]$ | 根から $v$ への辺重みの和 |
| $\text{lca}(u,v)$ | $u$ と $v$ の最近共通祖先 |
| $\text{dist}(u,v)$ | $\text{dep}[u] + \text{dep}[v] - 2\cdot\text{dep}[\text{lca}]$ |
Step 2: Tarjan Offline LCA の核心
DFS で頂点 $v$ を「離れる」タイミングで処理する。Union-Find で $v$ を親にマージし、ancestor[find(par)] = par で「現在の代表 = LCA 候補」を記録する。
# v の DFS 完了後
union(v, parent_of_v)
ancestor[find(parent_of_v)] = parent_of_v # 親が代表Step 3: 計算量
| 操作 | 計算量 |
|---|---|
| DFS | $O(N)$ |
| Union-Find 操作 | $O(\alpha(N))$ per query |
| 合計 | $O((N+Q)\alpha(N))$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ancestor 配列の更新忘れ | Union-Find の代表 ≠ LCA | ancestor[find(par)] = par |
| 再帰 DFS でスタックオーバーフロー | $N=2\times10^5$ では Python 再帰は危険 | 反復 DFS で実装 |
| 自己クエリ (u=v) の処理漏れ | 片側だけクエリ登録 | if u != v: で両側登録 |
次のステップ
- 発展問題: オンライン LCA（Binary Lifting $O(N \log N)$ 前処理・$O(\log N)$ クエリ）
- 発展問題: HLD + SegTree によるパス加算・最大値クエリ
- 参考: Tarjan (1979) "Applications of path compression on balanced trees"
自己評価
理解度: / /
自分の回答:
気づき・メモ: