Day 020-Q1 — Heavy-Light Decomposition

2026-05-03 赤色 Master / Phase 8+ ★★★★★★★★★ HLD パスクエリ

問題

$N$ 頂点の根付き木が与えられ、各頂点 $i$ には初期値 $a_i$ がある。Qクエリ：

  • 1 u v x: u-v パス上の全頂点に $x$ を加算
  • 2 u v: u-v パス上の値の最大値を出力

制約

$2 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$-10^9 \le a_i, x \le 10^9$

入出力例

入力例 1

7 5
1 3 2 4 5 2 3
1 1 2 2 3 3
1 4 6 10
2 4 6
1 2 7 -3
2 1 7
2 5 6

出力例 1

17
3
12

ヒント (段階的開示)

ヒント1: 方向性
木上のパスクエリは HLD で $O(\log^2 N)$ に。各ノードを DFS の Heavy path に沿って配列に並べ直すと、パスが連続区間に分解できる。
ヒント2: アプローチ
1. HLD で DFS 順インデックス。2. パスを $O(\log N)$ 個の連続区間に分解。3. 区間加算+区間最大値の遅延伝播セグメント木。
ヒント3: 誘導 
def path_query(u, v):
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]: u, v = v, u
        ans = max(ans, range_max(pos[head[u]], pos[u]))
        u = parent[head[u]]
    if depth[u] > depth[v]: u, v = v, u
    return max(ans, range_max(pos[u], pos[v]))

模範解答 (Python)

import sys
from sys import stdin
input = stdin.readline

def main():
    import sys
    sys.setrecursionlimit(300000)
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    parents = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for i in range(1, N):
        p = parents[i-1] - 1
        adj[p].append(i); adj[i].append(p)

    parent = [-1] * N
    depth = [0] * N
    sz = [1] * N
    heavy = [-1] * N
    order = []
    visited = [False] * N
    stack = [0]
    while stack:
        v = stack[-1]
        if not visited[v]:
            visited[v] = True
            order.append(v)
            for u in adj[v]:
                if u != parent[v]:
                    parent[u] = v; depth[u] = depth[v] + 1; stack.append(u)
        else:
            stack.pop()
    for v in reversed(order):
        max_sz = 0
        for u in adj[v]:
            if u != parent[v]:
                sz[v] += sz[u]
                if sz[u] > max_sz: max_sz = sz[u]; heavy[v] = u

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

    size = 1
    while size < N: size <<= 1
    seg = [-10**18] * (2 * size)
    lazy = [0] * (2 * size)
    for v in range(N):
        seg[size + pos[v]] = A[v]
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2*i], seg[2*i+1])

    def push_down(i):
        if lazy[i] != 0:
            for c in [2*i, 2*i+1]:
                seg[c] += lazy[i]; lazy[c] += lazy[i]
            lazy[i] = 0

    def range_add(l, r, val, node=1, lo=0, hi=None):
        if hi is None: hi = size - 1
        if r < lo or hi < l: return
        if l <= lo and hi <= r:
            seg[node] += val; lazy[node] += val; return
        push_down(node)
        mid = (lo + hi) // 2
        range_add(l, r, val, 2*node, lo, mid)
        range_add(l, r, val, 2*node+1, mid+1, hi)
        seg[node] = max(seg[2*node], seg[2*node+1])

    def range_max(l, r, node=1, lo=0, hi=None):
        if hi is None: hi = size - 1
        if r < lo or hi < l: return -10**18
        if l <= lo and hi <= r: return seg[node]
        push_down(node)
        mid = (lo + hi) // 2
        return max(range_max(l, r, 2*node, lo, mid),
                   range_max(l, r, 2*node+1, mid+1, hi))

    def path_update(u, v, val):
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]: u, v = v, u
            range_add(pos[head[u]], pos[u], val)
            u = parent[head[u]]
        if depth[u] > depth[v]: u, v = v, u
        range_add(pos[u], pos[v], val)

    def path_query(u, v):
        ans = -10**18
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]: u, v = v, u
            ans = max(ans, range_max(pos[head[u]], pos[u]))
            u = parent[head[u]]
        if depth[u] > depth[v]: u, v = v, u
        return max(ans, range_max(pos[u], pos[v]))

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, u, v, x = line
            path_update(u-1, v-1, x)
        else:
            _, u, v = line
            out.append(path_query(u-1, v-1))

    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

1HLDの基本概念
各頂点の Heavy child = 最も部分木サイズが大きい子。根から葉までで Heavy edge を $O(\log N)$ 回以上通らない。
2DFS順インデックスの割当
Heavy child 優先 DFS で同じチェーン上の頂点が連続インデックス。
3パス分解
head[u] != head[v] の間、深い側を切り離してSegment Tree に。同じchainでLCAまでの区間。
4遅延伝播セグメント木
区間加算・区間最大値を $O(\log N)$。HLDと組み合わせて $O(\log^2 N)$。

計算量

前処理: $O(N)$
クエリ1件: $O(\log^2 N)$
全体: $O((N + Q) \log^2 N)$

よくあるミス

ミス原因正しい書き方
再帰が深すぎてMLE/RTE再帰DFSiterative DFSを使う
chainの先頭更新ミスheadの管理ミスheavy childはhead継承、light childは自身がhead
パス分解でLCAを2回通るu==v判定漏れループ後に pos[u]→pos[v] まで処理
Lazy pushdownのタイミングミスseg/lazy更新順序子ノード更新前に必ずpush_down

次のステップ

  • 発展: HLD + 辺重みクエリ（辺を子頂点に持たせる変形）
  • Top Tree / Euler Tour Tree による動的木への発展

自己評価

自分の回答

気づき・メモ