Day 112-Q1 | Top Tree（トップツリー）

問題

$N$頂点の木があり、$i$番目（$1\le i\le N-1$）の辺は頂点$u_i,v_i$を結び重み$w_i$を持つ。$Q$個のクエリ0 i w（$i$番目の辺の重みを$w$に変更）と1 u v（$u$から$v$への単純パス上の辺重みの最大値を出力）を順に処理せよ。

入力形式

N Q
u_1 v_1 w_1
...
u_{N-1} v_{N-1} w_{N-1}
query_1
...
query_Q

制約

$2 \le N \le 2\times10^5$

$1 \le Q \le 2\times10^5$

$1 \le w_i \le 10^9$

クエリ1では $u \neq v$

入出力例

入力例1

出力例1

5
3
9

パス2→1→3→4上の辺重み3,5,2→最大5。2番目の辺(1-3)を重み1に更新後、同パスは3,1,2→最大3。パス4→3→5は2,9→最大9。

概念図: 木をheavy pathに分解してクラスタ化する

ヒント（段階的開示）

ヒント1: 方向性

クエリのたびにBFS/DFSでパスをたどると$O(N)$かかり全体$O(NQ)$で間に合わない。木を「クラスタ」に分解し、階層的に合成することで更新もクエリも$O(\log N)$程度に抑える。Top Treeはこの発想を一般化したデータ構造で、compress（パス合成）とrake（分岐合成）でボトムアップにクラスタ木を作る。

ヒント2: アプローチ

汎用Top Treeの実装はPythonでは非現実的だが、今回の「辺重み更新+パス最大値」だけならHeavy-Light Decomposition（HLD）+セグメント木で実用的に実現できる。これは「compressクラスタ=1本のheavy path」に固定した簡易版とみなせる。heavy pathを一直線の配列にまとめ、辺の重みは深い方の頂点の位置に格納。パスクエリはheadを辿りながら区間maxを合成する。

ヒント3: 誘導（コード骨格）

def path_max(u, v):
    res = NEG
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]:
            u, v = v, u
        res = max(res, query(pos[head[u]], pos[u]))
        u = parent[head[u]]
    if depth[u] > depth[v]: u, v = v, u
    if u != v: res = max(res, query(pos[u]+1, pos[v]))
    return res

模範解答 (Python)

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1

    edges = []
    g = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        edges.append([u, v, w])
        g[u].append((v, i))
        g[v].append((u, i))

    parent = [0] * (N + 1)
    depth = [0] * (N + 1)
    subsz = [1] * (N + 1)
    parent_edge = [-1] * (N + 1)
    order = []

    visited = [False] * (N + 1)
    stack = [1]
    visited[1] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v, ei in g[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                parent_edge[v] = ei
                depth[v] = depth[u] + 1
                stack.append(v)

    for u in reversed(order):
        if parent[u] != 0:
            subsz[parent[u]] += subsz[u]

    heavy = [0] * (N + 1)
    for u in order:
        best, bestsz = 0, 0
        for v, ei in g[u]:
            if v != parent[u] and subsz[v] > bestsz:
                bestsz, best = subsz[v], v
        heavy[u] = best

    head = [0] * (N + 1)
    pos = [0] * (N + 1)
    cur = 0
    todo = [(1, 1)]
    while todo:
        u, h = todo.pop()
        while u != 0:
            head[u] = h
            pos[u] = cur
            cur += 1
            for v, ei in g[u]:
                if v != parent[u] and v != heavy[u]:
                    todo.append((v, v))
            u = heavy[u]

    size = 1
    while size < N:
        size *= 2
    NEG = -(1 << 62)
    seg = [NEG] * (2 * size)

    def update(i, val):
        i += size
        seg[i] = val
        i //= 2
        while i:
            seg[i] = seg[2*i] if seg[2*i] > seg[2*i+1] else seg[2*i+1]
            i //= 2

    def query(l, r):
        res = NEG
        l += size; r += size + 1
        while l < r:
            if l & 1:
                if seg[l] > res: res = seg[l]
                l += 1
            if r & 1:
                r -= 1
                if seg[r] > res: res = seg[r]
            l //= 2; r //= 2
        return res

    edge_pos = [0] * (N - 1)
    for v in range(1, N + 1):
        if parent[v] != 0:
            ei = parent_edge[v]
            edge_pos[ei] = pos[v]
            update(pos[v], edges[ei][2])

    def path_max(u, v):
        res = NEG
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]:
                u, v = v, u
            res = max(res, query(pos[head[u]], pos[u]))
            u = parent[head[u]]
        if u == v:
            return res
        if depth[u] > depth[v]:
            u, v = v, u
        return max(res, query(pos[u] + 1, pos[v]))

    out = []
    for _ in range(Q):
        t = input_data[idx]; idx += 1
        if t == b"0":
            i = int(input_data[idx]); idx += 1
            w = int(input_data[idx]); idx += 1
            edges[i - 1][2] = w
            update(edge_pos[i - 1], w)
        else:
            u = int(input_data[idx]); idx += 1
            v = int(input_data[idx]); idx += 1
            out.append(str(path_max(u, v)))

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

main()

計算量: 前処理$O(N)$、更新$O(\log N)$、パスクエリ$O(\log^2 N)$（ジャンプ回数$\times$セグ木クエリ）。$N=Q=2\times10^5$規模のランダムテストでBFSベースの参照実装と全出力が一致することを確認済み。

Step-by-Step 解説

1部分木サイズとheavy childを求める
iterative DFSで訪問順を記録し逆順に部分木サイズを積み上げ、最大の子部分木を持つ子をheavy childとする。

2heavy path分解でセグ木上の連続領域を作る
heavy childを優先的に辿ることで同一heavy pathの頂点をposで連続させ、区間maxクエリに落とし込める。

3辺の重みを深い方の頂点の位置に格納する
辺$(parent[v],v)$の重みは$pos[v]$に格納。これにより`query(pos[a]+1,pos[b])`がちょうど$a\to b$間の辺のみを走査する。

4heavy pathをジャンプしながらパスを分解する
異なるheavy pathの間は浅い方のheadまでの区間maxを取りheadの親へジャンプ。同じpathに入ったら残り区間を1回処理して終了。

5Top Treeとの対応
1つのheavy path=1つのcompressクラスタ、軽い辺での分岐=rakeクラスタとみなせる、Top Treeの静的近似版。

よくあるミス

ミス	原因	正しい書き方
辺の重みを親頂点の位置に格納する	「辺」と「頂点」を混同する	辺$(parent[v],v)$の重みは子側$pos[v]$に格納する
`query(pos[u],pos[v])`としてu自身の位置も含める	uがLCAのとき、uの位置には親への辺の重みが乗る可能性がある	最終区間は`query(pos[u]+1,pos[v])`としてu自身を除く
HLD分解を再帰で書きRecursionErrorになる	鎖状の木で再帰深さがO(N)に達する	iterativeスタックでheavy pathを辿りながら分解する
heavy child判定を`>=`にして候補が不安定になる	厳密な最大を選ばずHLDの連続性が崩れうる	`>`で厳密に最大の子を選ぶ

次のステップ

発展: 本物のself-adjusting top treeを実装し、Link-Cut Treeより汎用的な部分木集約クエリに対応させる
発展: このHLD構成に区間加算・区間和を持たせ、遅延伝播セグメント木と組み合わせる
発展: 頂点重みクエリに変更しLCAを含む区間の扱いを比較する

自己評価

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

Day 112-Q1 — Top Tree（トップツリー・クラスタ収縮による動的木のパス最大値クエリ）

問題