Day 091-Q1 — Heavy-Light Decomposition + 遅延セグメント木（パス区間加算・パス区間和）

2026-07-14 赤色 Master / Phase 8+ ★★★★★★★★★ HLD・パスクエリ・遅延伝播

問題

$N$ 頂点の木（根は頂点1）と各頂点の初期値 $a_i$ が与えられる。1 u v x（パス $u$–$v$ 上の全頂点に $x$ 加算）と 2 u v（パス $u$–$v$ 上の頂点値の総和を出力）の $Q$ クエリを処理する。

制約

パラメータ範囲備考
$N, Q$$1 \le N, Q \le 2\times10^5$頂点数・クエリ数
$a_i, x$$0 \le a_i, x \le 10^9$頂点値・加算値
辺—木を成すことが保証

入出力例

入力例1

5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
1 2 5 10
2 2 5
2 1 4

出力例1

27
17

パス(2,5)に10加算 → 12+15=27。パス(1,4)は 1+12+4=17。

概念図

木を heavy chain に分解し、パスを O(log N) 本の連続区間に 1 2 3 4 5 heavy pos 配列（鎖ごとに連続） 1 2 4 chain(1,2,4) : 連続 3 5 パス(2,5): [pos2..pos2]+[pos5] → 2区間で処理

ヒント

ヒント1（方向性）

木のパスクエリを配列の区間クエリに落とし込む。重い辺でつながる鎖に分解すると、任意パスは $O(\log N)$ 本の連続区間の和で表せる。

ヒント2（アプローチ）

HLD で各頂点にセグ木上の連続位置 pos[v] を割り当て、区間加算・区間和を遅延伝播セグメント木で処理する。パス全体は $O(\log^2 N)$。

ヒント3（ほぼ答え） 
while head[u] != head[v]:
    if depth[head[u]] < depth[head[v]]:
        u, v = v, u
    apply(pos[head[u]], pos[u])   # 深い側の鎖の一部
    u = parent[head[u]]
if depth[u] > depth[v]:
    u, v = v, u
apply(pos[u], pos[v])            # 同一鎖

模範解答

import sys
input = sys.stdin.buffer.read

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(data[idx]); idx += 1
    g = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        g[u].append(v); g[v].append(u)

    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    size = [1] * (n + 1)
    heavy = [0] * (n + 1)
    order = []
    visited = [False] * (n + 1)
    stack = [1]; visited[1] = True
    while stack:
        x = stack.pop()
        order.append(x)
        for y in g[x]:
            if not visited[y]:
                visited[y] = True
                parent[y] = x
                depth[y] = depth[x] + 1
                stack.append(y)
    # 帰りがけ（order 逆順）で部分木サイズと heavy child を確定
    for x in reversed(order):
        best = 0
        for y in g[x]:
            if y != parent[x]:
                size[x] += size[y]
                if size[y] > best:
                    best = size[y]; heavy[x] = y

    head = [0] * (n + 1)
    pos = [0] * (n + 1)
    cur = 0
    # 鎖の先頭からの反復分解（再帰なし）
    st = [(1, 1)]
    while st:
        v, h = st.pop()
        while v:
            head[v] = h
            pos[v] = cur; cur += 1
            for y in g[v]:
                if y != parent[v] and y != heavy[v]:
                    st.append((y, y))   # 軽い子は新しい鎖の先頭
            v = heavy[v]

    # base 配列（pos 順）
    base = [0] * n
    for v in range(1, n + 1):
        base[pos[v]] = a[v]

    # 遅延伝播セグメント木（区間加算・区間和）
    seg = [0] * (4 * n)
    lazy = [0] * (4 * n)

    def build(node, lo, hi):
        if lo == hi:
            seg[node] = base[lo]; return
        mid = (lo + hi) // 2
        build(2*node, lo, mid); build(2*node+1, mid+1, hi)
        seg[node] = seg[2*node] + seg[2*node+1]
    build(1, 0, n - 1)

    def push(node, lo, hi):
        if lazy[node]:
            mid = (lo + hi) // 2
            for ch, l, r in ((2*node, lo, mid), (2*node+1, mid+1, hi)):
                lazy[ch] += lazy[node]
                seg[ch] += lazy[node] * (r - l + 1)
            lazy[node] = 0

    def update(node, lo, hi, l, r, val):
        if r < lo or hi < l: return
        if l <= lo and hi <= r:
            seg[node] += val * (hi - lo + 1)
            lazy[node] += val
            return
        push(node, lo, hi)
        mid = (lo + hi) // 2
        update(2*node, lo, mid, l, r, val)
        update(2*node+1, mid+1, hi, l, r, val)
        seg[node] = seg[2*node] + seg[2*node+1]

    def query(node, lo, hi, l, r):
        if r < lo or hi < l: return 0
        if l <= lo and hi <= r: return seg[node]
        push(node, lo, hi)
        mid = (lo + hi) // 2
        return query(2*node, lo, mid, l, r) + query(2*node+1, mid+1, hi, l, r)

    out = []
    for _ in range(q):
        t = int(data[idx]); idx += 1
        if t == 1:
            u = int(data[idx]); v = int(data[idx]); x = int(data[idx]); idx += 3
            while head[u] != head[v]:
                if depth[head[u]] < depth[head[v]]:
                    u, v = v, u
                update(1, 0, n-1, pos[head[u]], pos[u], x)
                u = parent[head[u]]
            if depth[u] > depth[v]:
                u, v = v, u
            update(1, 0, n-1, pos[u], pos[v], x)
        else:
            u = int(data[idx]); v = int(data[idx]); idx += 2
            s = 0
            while head[u] != head[v]:
                if depth[head[u]] < depth[head[v]]:
                    u, v = v, u
                s += query(1, 0, n-1, pos[head[u]], pos[u])
                u = parent[head[u]]
            if depth[u] > depth[v]:
                u, v = v, u
            s += query(1, 0, n-1, pos[u], pos[v])
            out.append(str(s))
    sys.stdout.write('\n'.join(out) + '\n')

main()

Step-by-Step 解説

Step 1: 反復DFSで parent/depth/size/heavy を求める

再帰DFSはパス状の木で $O(N)$ 深度になり RecursionError。行きがけで order を作り逆順で部分木サイズを積み、最大部分木の子を heavy とする。

Step 2: 鎖ごとに連続位置 pos を割り当てる

鎖の先頭から heavy child をたどる while ループで連続採番する。while 中は同じ鎖しか触らないため鎖内位置が必ず連続する。

Step 3: 遅延伝播セグメント木で区間加算・区間和

操作意味
update(l, r, x)区間に $x$ 加算（seg に区間長×x を反映）
query(l, r)区間和を返す

Step 4: パスを O(log N) 本の区間に分解

head[u] != head[v] の間、深い側の鎖を処理して親へジャンプ。最後に同一鎖の両端点区間を処理する（頂点重みなので両端含む）。

よくあるミス

ミス原因正しい書き方
再帰DFSで RecursionErrorパス状の木で深さ $N$反復DFSで前処理
区間加算で区間長を掛け忘れる点加算と混同seg[node] += val*(hi-lo+1)
浅い側の鎖を先に処理depth[head] の比較ミス常に head が深い方を処理して上る
頂点重み/辺重みの混同LCA を二重加算 or 除外ミス頂点重みは同一鎖で両端含む

次のステップ

  • 発展: パス最大値・パス区間代入（assign の遅延）へ拡張
  • 発展: 辺重み版（pos[u]+1 開始で LCA を除外）に書き換え
  • 次回予告: 最小費用流（MCMF）

自己評価

理解度: / /

自分の回答:

気づき・メモ: