Day 154-Q1 | Heavy-Light Decomposition（HLD・重軽分解）

問題

$N$ 頂点の木が与えられる（頂点1が根）。各頂点 $i$ には初期値 $a_i$ が設定されている。以下の2種類のクエリを $Q$ 個処理せよ。

1 u v: 頂点 $u$ から頂点 $v$ への単純パス上にある頂点の値の最大値を出力する
2 v x: 頂点 $v$ の値を $x$ に更新する

入力形式

N
u_1 v_1
...
u_{N-1} v_{N-1}
a_1 a_2 ... a_N
Q
query_1
...
query_Q

制約

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

$1 \le a_i, x \le 10^9$

木は連結

入出力例

入力例1

7
1 2
1 3
2 4
2 5
3 6
3 7
3 1 4 1 5 9 2
3
1 5 7
2 6 100
1 4 6

出力例1

5
100

概念図：チェイン分解（重い辺＝太線）

ヒント（段階的開示）

ヒント1（方向性）

毎回のパスクエリで愚直に頂点を1つずつ辿ると、木が一直線（パスグラフ）に近い形のとき1クエリ $O(N)$ かかり、$Q$ 回で $O(NQ)$ になり間に合わない。木を「配列に埋め込む」方法を考える。

ヒント2（アプローチ）

各頂点の部分木サイズを計算し、最大の部分木を持つ子（重い子）を1本だけ選ぶ。重い辺だけを辿ってできる道（チェイン）で頂点を並べると、任意の頂点から根までのパスは軽い辺を高々 $O(\log N)$ 回しか通らない（軽い辺を1回通るたびに部分木サイズが半分以下になるため）。パスクエリは「チェインの先頭が異なる間、深い方のチェインを丸ごと配列区間としてセグ木に問い合わせて根方向へジャンプする」処理に分解できる。

ヒント3（誘導）

# 1. 部分木サイズ計算 → 各頂点の重い子 heavy[u] を決定
# 2. head[u]（uが属するチェインの先頭）, pos[u]（配列上の位置）をDFSで採番
#    重い子は同じチェイン（head を親から引き継ぐ）、軽い子は新しいチェインを開始
# 3. pos[] の順に a[] を並べた配列にセグ木（区間max・点更新）を構築
# 4. path_max(u, v):
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]]
res = max(res, query(pos[min(u,v,key=depth)], pos[max(u,v,key=depth)]))

模範解答 (Python)

import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline


def main():
    N = int(input())
    g = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
    a = [0] + list(map(int, input().split()))

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

    size = [1] * (N + 1)
    heavy = [0] * (N + 1)
    for u in reversed(order):
        best = 0
        for v in g[u]:
            if v != parent[u]:
                size[u] += size[v]
                if size[v] > best:
                    best = size[v]
                    heavy[u] = v

    head = [0] * (N + 1)
    pos = [0] * (N + 1)
    base = [0] * N
    cnt = 0

    def decompose(u, h):
        nonlocal cnt
        head[u] = h
        pos[u] = cnt
        base[cnt] = a[u]
        cnt += 1
        if heavy[u]:
            decompose(heavy[u], h)
        for v in g[u]:
            if v != parent[u] and v != heavy[u]:
                decompose(v, v)

    decompose(1, 1)

    sz = 1
    while sz < N:
        sz *= 2
    NEG = -1 << 60
    seg = [NEG] * (2 * sz)
    for i in range(N):
        seg[sz + i] = base[i]
    for i in range(sz - 1, 0, -1):
        seg[i] = max(seg[2 * i], seg[2 * i + 1])

    def update(i, val):
        i += sz
        seg[i] = val
        i //= 2
        while i >= 1:
            seg[i] = max(seg[2 * i], seg[2 * i + 1])
            i //= 2

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

    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
        res = max(res, query(pos[u], pos[v]))
        return res

    Q = int(input())
    out = []
    for _ in range(Q):
        q = input().split()
        if q[0] == '1':
            u, v = int(q[1]), int(q[2])
            out.append(str(path_max(u, v)))
        else:
            v, x = int(q[1]), int(q[2])
            a[v] = x
            update(pos[v], x)
    print('\n'.join(out))


main()

Step-by-Step 解説

1部分木サイズと重い子の決定
入力例1で計算すると $size[4]=size[5]=size[6]=size[7]=1$、$size[2]=size[3]=3$、$size[1]=7$。頂点2の重い子は4、頂点3の重い子は6、頂点1の重い子は2に決まる（同点は先に見つかった方）。

2チェイン分解
DFS順で採番すると pos は 1→0, 2→1, 4→2, 5→3, 3→4, 6→5, 7→6。セグ木配列は [3,1,1,5,4,9,2]。頂点1,2,4が同一チェイン（head=1）、5・3,6・7がそれぞれ別チェイン。

3クエリ 1 5 7（更新前）
$u=5,v=7$ を辿る：区間 $[3,3]$（値5）→ $u=2$へ。head比較で入れ替え、区間 $[6,6]$（値2）→ $u=3$へ。区間 $[4,4]$（値4）→ $u=1$。最後に $head[u]=head[v]=1$ で区間 $[0,1]$（値3,1）。全候補 $\{5,2,4,3,1\}$ の最大は 5。頂点6は経路 $5\to2\to1\to3\to7$ に含まれない。

4更新後のクエリ 1 4 6
2 6 100 で update(pos[6]=5,100)。$u=4,v=6$：区間 $[4,5]$（値4,100）→ $u=1$。区間 $[0,2]$（値3,1,1）。全体最大は 100。

よくあるミス

ミス	原因	正しい書き方
decomposeを再帰で書きNが大きいとスタックオーバーフロー	木の高さがそのまま再帰深さになる	再帰上限を上げるか反復DFSに書き換える
浅い方・深い方の比較を depth[u] でやってしまう	頂点自身の深さとチェイン先頭の深さを混同	必ず depth[head[u]] 同士を比較する
query(pos[head[u]], pos[u]) の順序を逆と誤解	チェイン内でposが単調増加することを忘れる	常に pos[head[u]] <= pos[u] が成り立つ前提でよい
重い子の選び方で結果が変わると誤解	タイブレークの影響範囲の誤解	どの重い子を選んでも最終的な最大値クエリの結果は同じ、変わるのはチェイン形状のみ
更新クエリ後にセグ木だけ更新しa[]を更新し忘れる	元配列とセグ木の二重管理を怠る	他のクエリでaを参照する設計なら両方更新する

次のステップ

発展: パスの総和クエリや、パス上の一律加算を遅延セグ木と組み合わせて対応する。
次回予告: Cartesian Tree（デカルト木）

自己評価

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

Day 154-Q1 — Heavy-Light Decomposition（HLD・重軽分解）

問題