Day 043-Q2 | 木の直径クエリ（Euler Tour + SegTree マージ）

問題

$N$ 頂点の根付き木（根: 頂点1、辺重み付き）が与えられる。2種類のクエリを処理せよ。

制約

$2 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$1 \le w_i \le 10^9$

時間制限: 3sec / メモリ: 256MB

クエリ種別

種別	形式	意味
更新	`1 v w`	辺 $(v, \text{parent}(v))$ の重みを $w$ に変更
クエリ	`2 u v`	$\text{LCA}(u,v)$ を根とする部分木の直径

入出力例

入力例 1

出力例 1

7
14

概念図: 部分木直径のセグメント木マージ

ヒント（段階的開示）

ヒント1: 方向性

部分木の直径 = 部分木内の最遠頂点対の距離。Euler Tour で部分木を区間化し、セグメント木に $(diameter, max\_depth)$ を持たせてマージ演算で直径を合成する。

ヒント2: アプローチ

Euler Tour で各頂点の訪問順 tin[v]、退出時刻 tout[v] を記録
セグメント木の各ノードに (diam, max_depth) を保持
マージ: diam = max(L.diam, R.diam, L.max_depth + R.max_depth)
部分木クエリ: LCA を求め、その区間を range query

ヒント3: 実装骨格

def merge(a, b):
    if a == (INF, INF): return b
    if b == (INF, INF): return a
    d = max(a[0], b[0], a[1] + b[1])
    md = max(a[1], b[1])
    return (d, md)

# クエリ: LCA を根とする部分木の直径
r = lca(u, v)
result = query_range(1, 0, M-1, tin[r], tout[r])
print(result[0])  # diameter

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    parent = [0] * (N + 1)
    weight = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]

    for v in range(2, N + 1):
        p, w = map(int, input().split())
        parent[v] = p
        weight[v] = w
        children[p].append(v)

    order = []
    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    depth = [0] * (N + 1)
    timer = [0]

    stack = [(1, 0, False)]
    while stack:
        v, d, leaving = stack.pop()
        if leaving:
            tout[v] = timer[0] - 1
            continue
        tin[v] = timer[0]
        order.append(v)
        timer[0] += 1
        depth[v] = d
        stack.append((v, d, True))
        for c in reversed(children[v]):
            stack.append((c, d + weight[c], False))

    M = len(order)
    INF = -10**18
    seg = [(INF, INF)] * (4 * M)

    def merge(a, b):
        if a == (INF, INF): return b
        if b == (INF, INF): return a
        d = max(a[0], b[0], a[1] + b[1])
        md = max(a[1], b[1])
        return (d, md)

    def build(node, lo, hi):
        if lo == hi:
            v = order[lo]
            seg[node] = (0, depth[v])
            return
        mid = (lo + hi) >> 1
        build(2*node, lo, mid)
        build(2*node+1, mid+1, hi)
        seg[node] = merge(seg[2*node], seg[2*node+1])

    def update_pos(node, lo, hi, pos, val):
        if lo == hi:
            seg[node] = (0, val)
            return
        mid = (lo + hi) >> 1
        if pos <= mid:
            update_pos(2*node, lo, mid, pos, val)
        else:
            update_pos(2*node+1, mid+1, hi, pos, val)
        seg[node] = merge(seg[2*node], seg[2*node+1])

    def query_range(node, lo, hi, l, r):
        if r < lo or hi < l: return (INF, INF)
        if l <= lo and hi <= r: return seg[node]
        mid = (lo + hi) >> 1
        return merge(query_range(2*node, lo, mid, l, r),
                     query_range(2*node+1, mid+1, hi, l, r))

    build(1, 0, M-1)

    LOG = 18
    up = [[0] * (N + 1) for _ in range(LOG)]
    up[0] = parent[:]
    up[0][1] = 1
    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]

    dep_node = [0] * (N + 1)
    stk2 = [(1, 0)]
    while stk2:
        v, d = stk2.pop()
        dep_node[v] = d
        for c in children[v]:
            stk2.append((c, d+1))

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

    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            v, w = int(line[1]), int(line[2])
            delta = w - weight[v]
            weight[v] = w
            stk = [v]
            while stk:
                u = stk.pop()
                depth[u] += delta
                update_pos(1, 0, M-1, tin[u], depth[u])
                for c in children[u]:
                    stk.append(c)
        else:
            u, v = int(line[1]), int(line[2])
            r = lca(u, v)
            res = query_range(1, 0, M-1, tin[r], tout[r])
            print(res[0])

solve()

Step-by-Step 解説

1直径のマージ可能性
直径は「最遠頂点対の距離」。2部分木 A, B をマージすると直径候補は 3 通り：A内部・B内部・A最深+B最深。これがマージ演算 merge(L, R) の核心。

2セグメント木の設計
Euler Tour の訪問順に頂点を並べ、各頂点の根からの深さを値として格納。内部ノードは (diameter, max_depth) のペアを持つ。

3部分木クエリ
頂点 $r$ の部分木は Euler Tour 上の区間 $[\text{tin}[r], \text{tout}[r]]$。クエリ 2 u v では $r = \text{LCA}(u, v)$ を計算し、この区間の range query を呼ぶ。

4辺重み更新
辺 $(v, \text{parent}(v))$ の重みが変わると、$v$ の部分木全体の深さが $\Delta = w_{new} - w_{old}$ だけシフト。部分木の DFS + セグ木更新で対応。

計算量

構築: $O(N \log N)$（Euler Tour $O(N)$ + SegTree $O(N)$）
クエリ: $O(\log N)$（LCA + range query）
更新: $O(K \log N)$（$K$ = 部分木サイズ、最悪 $O(N \log N)$）
空間: $O(N \log N)$（Binary Lifting）

よくあるミス

ミス	原因	正しい書き方
LCA を間違えた部分木で計算	u, v 両方の LCA を根にすべき	`r = lca(u, v)`
merge で INF + INF がオーバーフロー	番兵値の設計ミス	空チェック（`if a == (INF, INF)`）
辺重み更新で部分木外の頂点も更新	tin/tout の範囲ミス	DFS で部分木のみ走査
depth の初期化を根=0 にしていない	BFS 忘れ	根の depth=0 を明示

次のステップ

発展問題: 辺追加/削除を含む動的木の直径（Link-Cut Tree）
類題: CF 600E "Lomsat gelral"、AOJ GRL_5_B
応用: ゲーム木・ネットワーク設計の最遠点管理

自己評価

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