Day 127-Q4 | 頂点追加オンライン木の直径維持

問題

頂点1のみからなる木を用意する。$i=2,\dots,N$ の順に、頂点$i$を既存の頂点$p_i$（$p_i直後の木の直径（辺重みの和での最遠2頂点間距離）を出力せよ。

入力形式

N
p_2 w_2
p_3 w_3
...
p_N w_N

制約

$2 \le N \le 100000$

$1 \le p_i < i$

$1 \le w_i \le 10^9$

入出力例

入力例1

出力例1

1
2
3

頂点2追加後:直径1(辺1-2)。頂点3追加後:2-3(1経由)=2で直径2。頂点4追加後:3-4(1経由)=3で直径3。

概念図

ヒント（段階的開示）

ヒント1（方向性）

毎回BFS/DFSで直径を再計算すると $O(N)$ かかり全体 $O(N^2)$ になり間に合わない。直径情報を差分更新できないか考える。

ヒント2（アプローチ）

木上のどの頂点から出発しても最遠頂点は必ずその木の何らかの直径の端点になる。現在の直径端点$(a,b)$を保持し、新頂点$v$との距離$dist(v,a),dist(v,b)$だけを見れば新しい直径が判定できる。距離クエリをLCAベースで$O(\log N)$にすれば全体$O(N\log N)$。

ヒント3（誘導）

$p_i<i$なので、頂点追加と同時にその場でダブリングテーブルを構築できる。

def add_vertex(v, p, w):
    up[0][v] = p
    depth_edges[v] = depth_edges[p] + 1
    dist_root[v] = dist_root[p] + w
    for k in range(1, LOG):
        up[k][v] = up[k-1][up[k-1][v]]

def dist(u, v):
    w = lca(u, v)
    return dist_root[u] + dist_root[v] - 2*dist_root[w]

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1

    LOG = max(1, (n).bit_length() + 1)
    up = [[0] * (n + 1) for _ in range(LOG)]
    depth_edges = [0] * (n + 1)
    dist_root = [0] * (n + 1)

    def lca(u, v):
        if depth_edges[u] < depth_edges[v]:
            u, v = v, u
        diff = depth_edges[u] - depth_edges[v]
        k = 0
        while diff:
            if diff & 1:
                u = up[k][u]
            diff >>= 1
            k += 1
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u, v = up[k][u], up[k][v]
        return up[0][u]

    def dist(u, v):
        w = lca(u, v)
        return dist_root[u] + dist_root[v] - 2 * dist_root[w]

    a, b = 1, 1
    diameter = 0
    out = []

    for i in range(2, n + 1):
        p = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1

        up[0][i] = p
        depth_edges[i] = depth_edges[p] + 1
        dist_root[i] = dist_root[p] + w
        for k in range(1, LOG):
            up[k][i] = up[k - 1][up[k - 1][i]]

        d_a = dist(i, a)
        d_b = dist(i, b)

        if d_a > diameter and d_a >= d_b:
            diameter = d_a
            b = i
        elif d_b > diameter:
            diameter = d_b
            a = i

        out.append(str(diameter))

    print('\n'.join(out))


solve()

Step-by-Step 解説

1直径端点の維持
直径を毎回全頂点走査せず、現在の直径を実現する2端点$(a,b)$だけを保持する。

2なぜ端点だけで十分か
木上のどの頂点から出発しても最遠頂点は必ず直径の端点になる補題により、新頂点の直径判定には旧端点との距離だけ見れば足りる。

3追加と同時にダブリング構築
$p_i<i$より祖先テーブルは追加時点で完成済みなので、オフライン前処理不要でその場で構築できる。

4LCAで距離計算
dist(u,v)=dist_root[u]+dist_root[v]-2*dist_root[lca(u,v)]で$O(\log N)$。

5端点の更新規則
dist(i,a),dist(i,b)のうち直径を超える方があれば、大きい方の端点を$i$に置き換える。

よくあるミス

ミス	原因	正しい書き方
d_a・d_b両方超えたときの優先順位を誤る	次回以降に不適切な端点を残す	`d_a >= d_b`で大きい方を明示的に選ぶ
ダブリングのLOGをNに対して不足させる	ビット長ぎりぎりで確保	`LOG=N.bit_length()+1`で余裕を持たせる
頂点1のみの初期直径・端点の初期化忘れ	a=b=1,diameter=0を設定していない	ループ開始前に必ず初期化する
depth_edgesとdist_rootを混同	変数名を使い分けない	LCA探索はdepth_edges、距離計算はdist_rootと役割分離

次のステップ

発展: 辺の重み変更にも対応する動的木直径維持（Link-Cut Treeによるモノイドマージ）
次回予告: 隣接行列のトレースによる閉路数え上げ（行列累乗 O(N^3 log K)）

自己評価

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

Day 127-Q4 — 頂点追加オンライン木の直径維持

問題