Day 054-Q2 | HLD + 遅延SegTree（辺重みパス最大値・区間加算）

問題

$N$ 頂点の根付き木（根: 頂点 $1$）が与えられる。各辺 $(u, v)$ には初期重み $w_{uv}$ がある。

以下の $Q$ クエリを処理せよ:

Type 1: 1 u v x — 辺 $(u, v)$ の重みに $x$ を加算する
Type 2: 2 u v — 頂点 $u$ から頂点 $v$ へのパス上の辺重みの最大値を出力する

制約

パラメータ	範囲
$N$	$2 \le N \le 10^5$
$Q$	$1 \le Q \le 10^5$
$w_i$	$0 \le w_i \le 10^9$（初期値）
$x$	$\|x\| \le 10^9$（負加算あり）
答えの範囲	$[-10^{18}, 10^{18}]$

入出力例

入力例 1

出力例 1

5
13
8

クエリ1: パス1→2→4の辺 (w=3,w=1) の最大=5（辺1-3が5）。クエリ2: 辺1-2に+10→13。クエリ3: パス3→1→2→4で最大=13（次は1-3=5, 1-2=13, 2-4=1）→13... 再確認が必要。

概念図: HLD による木のパス分解

ヒント（段階的開示）

ヒント1: 方向性

辺重みを「子ノードの頂点重み」として管理する。これにより辺クエリを頂点クエリに変換できる。HLD でパスを $O(\log N)$ 区間に分解し、遅延SegTree で区間加算・区間最大値クエリを処理する。

ヒント2: アプローチ

辺 $(u, v)$ の辺重みを 深い方（子側）の頂点重み として管理
HLD でオイラーツアー順に頂点を並べ、SegTree 上でクエリ処理
パスクエリは LCA まで HLD チェーンを辿りながら区間に分解
辺クエリのため LCA の頂点重みは除外（pos[LCA]+1 から）

ヒント3: パスクエリの骨格

def path_max(u, v):
    res = -INF
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]:
            u, v = v, u
        # head[u] から u までの区間をクエリ
        res = max(res, seg_query(pos[head[u]], pos[u]))
        u = parent[head[u]]  # チェーンの親へ
    # 同じチェーン内: 浅い方が LCA
    if depth[u] > depth[v]:
        u, v = v, u
    # u が LCA: 辺クエリなので pos[u]+1 から
    if u != v:
        res = max(res, seg_query(pos[u]+1, pos[v]))
    return res

模範解答 (Python)

import sys
input = sys.stdin.readline

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

    parent = [0]*(N+1); depth = [0]*(N+1)
    sz = [1]*(N+1); heavy = [-1]*(N+1)
    head = [0]*(N+1); pos = [0]*(N+1)
    node_weight = [0]*(N+1)  # 辺重みを子ノードに割り当て

    # DFS1: sz, heavy, depth, parent
    visited = [False]*(N+1)
    stack = [(1, 0, False)]
    order = []
    while stack:
        v, p, post = stack.pop()
        if post:
            if p:
                sz[p] += sz[v]
                if heavy[p] == -1 or sz[v] > sz[heavy[p]]:
                    heavy[p] = v
            continue
        if visited[v]: continue
        visited[v] = True
        order.append(v)
        stack.append((v, p, True))
        parent[v] = p
        for u, eid, w in adj[v]:
            if u != p:
                depth[u] = depth[v] + 1
                node_weight[u] = w  # 辺の重みを子に割り当て
                stack.append((u, v, False))

    # DFS2: HLD
    cur = 0
    stack2 = [(1, 1)]
    while stack2:
        v, h = stack2.pop()
        head[v] = h
        pos[v] = cur
        cur += 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))

    # Lazy SegTree（区間加算・区間最大値）
    INF = float('inf')
    size = 1
    while size < N: size <<= 1
    seg = [-INF] * (2*size)
    lazy = [0] * (2*size)

    for v in range(1, N+1):
        seg[size + pos[v]] = node_weight[v] if parent[v] != 0 else -INF
    for i in range(size-1, 0, -1):
        seg[i] = max(seg[2*i], seg[2*i+1])

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

    def update(l, r, val, k=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:
            if seg[k] != -INF: seg[k] += val
            lazy[k] += val; return
        push_down(k); mid = (lo+hi)>>1
        update(l, r, val, 2*k, lo, mid)
        update(l, r, val, 2*k+1, mid+1, hi)
        seg[k] = max(seg[2*k], seg[2*k+1])

    def query(l, r, k=1, lo=0, hi=None):
        if hi is None: hi = size-1
        if r < lo or hi < l: return -INF
        if l <= lo and hi <= r: return seg[k]
        push_down(k); mid = (lo+hi)>>1
        return max(query(l, r, 2*k, lo, mid), query(l, r, 2*k+1, mid+1, hi))

    def path_max(u, v):
        res = -INF
        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

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, eu, ev, x = line
            child = eu if depth[eu] > depth[ev] else ev
            update(pos[child], pos[child], x)
        else:
            _, u, v = line
            out.append(path_max(u, v))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1辺重みを子ノードに変換
辺 $(u, v)$ の重みを深い方（子側）の頂点重みとして持つ。根の頂点重みは存在しない（-INF）。これにより辺クエリを頂点クエリと同一視できる。

2HLD（Heavy-Light Decomposition）
サブツリーサイズ最大の子を heavy edge でチェーンにつなぐ。任意のパスは高々 $O(\log N)$ 個の heavy chain の連続部分に分解される。

3遅延セグメント木（区間加算・区間最大値）
lazy に加算値を保持し、push_down で子に伝播。区間最大値クエリは標準的。辺クエリでは LCA の頂点重みを除くため pos[LCA]+1 から始める。

4辺の更新
辺 $(u, v)$ の更新では子側（深い方）の頂点インデックスを特定し、SegTree の 1 点を更新する。

計算量

HLD 前処理: $O(N)$
各クエリ: $O(\log^2 N)$ — HLD $O(\log N)$ チェーン × SegTree $O(\log N)$
全体: $O((N + Q) \log^2 N)$

よくあるミス

ミス	原因	正しい書き方
LCA の頂点重みを含める	LCA は共有点で辺ではない	`query(pos[u]+1, pos[v])`
push_down を忘れる	lazy が子に伝播されない	update/query の descent で push_down
heavy child を正しく特定しない	sz 最大の子の比較ミス	`sz[v] > sz[heavy[p]]`
辺の深さ判定ミス	親が深い方に辺重みを付ける	`child = eu if depth[eu] > depth[ev] else ev`

次のステップ

発展問題: 辺の削除・追加を含む動的木 → Link-Cut Tree
関連: パス上の辺重みの GCD クエリ（GCD モノイド SegTree）
応用: HLD + 区間 XOR クエリ（セグメント木の演算をXORに変更）

自己評価

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