問題
$N$ 頂点の重み付き根付き木（根: 頂点1）が与えられる。辺 $(p_v, v)$ の重みは $c_{p_v,v}$。
$Q$ 個のクエリに答えよ。各クエリで頂点 $v$ が指定され、頂点 $v$ の部分木内の最長パス（直径）の長さを出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $2 \le N \le 2 \times 10^5$ |
| $c_{uv}$ | $1 \le c_{uv} \le 10^9$ |
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
入出力例
入力例 1
7
1 3
1 2
2 4
2 1
3 5
3 6
4
1
2
3
6出力例 1
17
11
11
0頂点1の部分木 = 全体。頂点6の部分木 = 葉のみ（直径0）。
概念図: 部分木直径マージのイメージ
ヒント（段階的開示）
ヒント1: 方向性
各頂点 $v$ に「$v$ から部分木内最遠点距離 (
max_depth)」と「$v$ の部分木内最長パス (diameter)」の2値を DFS のポストオーダーで計算する。
ヒント2: アプローチ
子 $c$ のマージ順に：
diameter[v] = max(diameter[v], diameter[c], max_depth[v] + max_depth[c] + w)max_depth[v] = max(max_depth[v], max_depth[c] + w)
ヒント3: コード骨格（反復DFS）
stack = [(1, False)]
while stack:
v, processed = stack.pop()
if processed:
for ch, w in children[v]:
cand = max_depth[v] + max_depth[ch] + w
diameter[v] = max(diameter[v], diameter[ch], cand)
max_depth[v] = max(max_depth[v], max_depth[ch] + w)
else:
stack.append((v, True))
for ch, w in children[v]:
stack.append((ch, False))模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N = int(input())
children = [[] for _ in range(N + 1)]
for v in range(2, N + 1):
tokens = input().split()
p, c = int(tokens[0]), int(tokens[1])
children[p].append((v, c))
max_depth = [0] * (N + 1)
diameter = [0] * (N + 1)
# Iterative post-order DFS
stack = [(1, False)]
while stack:
v, processed = stack.pop()
if processed:
for ch, w in children[v]:
cand = max_depth[v] + max_depth[ch] + w
if cand > diameter[v]:
diameter[v] = cand
if diameter[ch] > diameter[v]:
diameter[v] = diameter[ch]
d = max_depth[ch] + w
if d > max_depth[v]:
max_depth[v] = d
else:
stack.append((v, True))
for ch, w in children[v]:
stack.append((ch, False))
Q = int(input())
out = []
for _ in range(Q):
v = int(input())
out.append(str(diameter[v]))
print('\n'.join(out))
main()Step-by-Step 解説
Step 1: ポストオーダー DFS で2値を管理
葉では max_depth = 0, diameter = 0。親 $v$ で子 $c$（辺重み $w$）をマージする際、max_depth[v] + max_depth[c] + w が「$v$ を通るパス」の候補長となる。これを diameter[v] の候補に加える。
Step 2: マージ順序の重要性
直径候補の計算を max_depth 更新の前に行うことが重要。更新後だと「今追加した子と同じ子」でパスを作る誤りが生じる。
Step 3: 反復スタック DFS
Python の再帰制限（デフォルト1000）を回避するため、明示スタック + processed フラグでポストオーダーを実装。計算量 $O(N + Q)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
max_depth 更新後に直径候補を計算 | 同一子との自己パスを作る | 直径計算 → max_depth 更新の順 |
| 再帰 DFS で MLE/TLE | N=2×10⁵ で Python 再帰制限 | 反復スタック DFS に変換 |
diameter[ch] の伝播を忘れる | 子の内部直径が親に引き継がれない | diameter[v] = max(diameter[v], diameter[ch]) |
次のステップ
- 発展問題: 辺重み変更 + 部分木直径クエリ（Link-Cut Tree による動的版）
- 関連: 全方位木DP（Rerooting）で各頂点を根とした場合の全体直径を $O(N)$ で算出