Day 075-Q1 | HLD + 遅延SegTree（パス区間加算・最大値クエリ）

問題

$N$ 頂点の根付き木（根: 0）が与えられる。各頂点 $v$ に値 $a_v$ が設定されており、以下の $Q$ 個のクエリを処理せよ。

クエリ 1: パス $u \to v$ 上のすべての頂点の値に $x$ を加算する
クエリ 2: パス $u \to v$ 上の頂点の値の最大値を出力する

制約

パラメータ	範囲	備考
$N$	$2 \le N \le 2 \times 10^5$	頂点数
$Q$	$1 \le Q \le 2 \times 10^5$	クエリ数
$a_i, x$	$-10^9 \le a_i, x \le 10^9$	初期値・加算値

入出力例

入力例1

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

出力例1

17
12

概念図: HLD による重いパス分解

赤い辺が heavy edge（部分木が最大の子への辺）。同一 heavy path 上の頂点は連続した pos 番号を持つため、SegTree の区間クエリに変換できる。

ヒント

ヒント1（方向性）

Heavy-Light Decomposition (HLD) で木のパスを $O(\log N)$ 個の連続区間に分解し、各区間を遅延セグメント木（区間加算・区間最大値）で処理する。計算量は $O((N + Q) \log^2 N)$。

ヒント2（アプローチ）

各頂点の部分木サイズ $\text{sz}[v]$ を計算し、最大の子を 重い子（heavy child） と定義する
重い子への辺を優先して DFS することで、連続した pos 番号（Euler tour 番号）を割り当てる
$u \to v$ パスを LCA まで辿りながら、各 heavy path の区間を遅延SegTree に渡す
遅延SegTree では lazy_add による区間加算と range_max クエリを実装する

ヒント3（ほぼ答え）

# パスクエリの核心
def path_query(seg, hld, u, v):
    res = -10**18
    while hld.head[u] != hld.head[v]:
        if hld.depth[hld.head[u]] < hld.depth[hld.head[v]]:
            u, v = v, u
        res = max(res, seg.query(hld.pos[hld.head[u]], hld.pos[u] + 1))
        u = hld.parent[hld.head[u]]
    if hld.depth[u] > hld.depth[v]:
        u, v = v, u
    res = max(res, seg.query(hld.pos[u], hld.pos[v] + 1))
    return res

模範解答

import sys
from math import inf
input = sys.stdin.readline

class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n: self.size <<= 1
        self.tree = [-inf] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)

    def build(self, a):
        for i, v in enumerate(a): self.tree[self.size + i] = v
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])

    def _push(self, i):
        if self.lazy[i]:
            for c in [2*i, 2*i+1]:
                self.tree[c] += self.lazy[i]
                self.lazy[c] += self.lazy[i]
            self.lazy[i] = 0

    def update(self, l, r, val, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l: return
        if l <= lo and hi <= r:
            self.tree[i] += val; self.lazy[i] += val; return
        self._push(i)
        mid = (lo + hi) >> 1
        self.update(l, r, val, 2*i, lo, mid)
        self.update(l, r, val, 2*i+1, mid, hi)
        self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])

    def query(self, l, r, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l: return -inf
        if l <= lo and hi <= r: return self.tree[i]
        self._push(i)
        mid = (lo + hi) >> 1
        return max(self.query(l, r, 2*i, lo, mid),
                   self.query(l, r, 2*i+1, mid, hi))

def solve():
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        adj[u].append(v); adj[v].append(u)

    # HLD 構築
    sz = [1]*N; heavy = [-1]*N; parent = [-1]*N; depth = [0]*N
    order = []; stack = [(0, -1)]
    while stack:
        v, p = stack.pop(); parent[v] = p; order.append(v)
        for u in adj[v]:
            if u != p: depth[u] = depth[v]+1; stack.append((u, v))
    for v in reversed(order):
        p = parent[v]
        if p != -1:
            sz[p] += sz[v]
            if heavy[p] == -1 or sz[v] > sz[heavy[p]]: heavy[p] = v

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

    seg = LazySegTree(N)
    init = [0]*N
    for v in range(N): init[pos[v]] = a[v]
    seg.build(init)

    def path_upd(u, v, val):
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]: u, v = v, u
            seg.update(pos[head[u]], pos[u]+1, val); u = parent[head[u]]
        if depth[u] > depth[v]: u, v = v, u
        seg.update(pos[u], pos[v]+1, val)

    def path_qry(u, v):
        res = -10**18
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]: u, v = v, u
            res = max(res, seg.query(pos[head[u]], pos[u]+1)); u = parent[head[u]]
        if depth[u] > depth[v]: u, v = v, u
        return max(res, seg.query(pos[u], pos[v]+1))

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1: path_upd(line[1], line[2], line[3])
        else: out.append(path_qry(line[1], line[2]))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: HLD の本質 — 重いパスの連続性

各頂点の 重い子（heavy child） を「部分木サイズ最大の子」と定義し、重い子への遷移を優先して DFS をすると、同じ heavy path 上の頂点が連続した pos 番号を持つ。任意のパスは $O(\log N)$ 個の heavy path 区間の列に分解される。

Step 2: 遅延SegTree — lazy_add の伝播

区間加算 + 区間最大値クエリ。lazy[i] は「子ノードにまだ伝播していない加算値」。子を参照する前に _push を呼んで遅延を解消する。update 後には tree[i] = max(tree[2i], tree[2i+1]) で親を更新する。

Step 3: パスクエリのループ

head[u] != head[v] の間は、深い方の head から現在位置までを区間クエリに変換し、parent[head[u]] へ移動する。同一 heavy path になったら残り区間を処理する。

よくあるミス

ミス	原因	正しい書き方
`head` の初期化ミス	DFS の順序が不正	重い子を最後に積んで先に展開する
`pos` の値が重複	タイマーをローカル変数で管理	リスト `timer = [0]` で参照渡し
`_push` 忘れ	遅延が残ったまま子を参照	子アクセス前に必ず `_push(i)`

次のステップ

発展問題: 辺重みに対する HLD クエリ（頂点ではなく辺に値を持たせる — 辺 $(u, v)$ の値を深い方の頂点 $v$ に付与して HLD を適用）

自己評価

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

自分の回答:

気づき・メモ: