Day 041-Q2 | Euler Tour + SegTree（部分木・パスクエリ・点更新）

問題

$N$ 頂点の根付き木（根は頂点 $1$）が与えられ、各頂点 $v$ に初期重み $w_v$ がある。以下のクエリを処理せよ：

1 v x : 頂点 $v$ の重みを $x$ に変更。
2 v : 頂点 $v$ の部分木の重みの総和を出力。
3 u v : 頂点 $u$ から $v$ へのパス上の重みの総和を出力（HLD使用）。

制約

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

$0 \le w_v, x \le 10^9$

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

出力例 1

15
9
22

概念図: Euler Tour と HLD の対応

ヒント（段階的開示）

ヒント1: 方向性

オイラーツアー（in-time / out-time）を用いると部分木 $v$ = 区間 $[\text{in}[v], \text{out}[v]]$ になり、セグメント木で部分木総和が $O(\log N)$ で処理できる。パスクエリはHLDで $O(\log^2 N)$。

ヒント2: アプローチ

DFSでin-time, out-timeを計算（Euler tour）。
セグメント木（点更新・区間和）を構築。
部分木クエリ: seg.query(in[v], out[v])
パスクエリ: HLD で重鎖を列挙し各区間をセグメント木でクエリ。

ヒント3: 実装骨格

# DFS (iterative) でオイラーツアー
def build_euler(adj, root, N):
    in_t = [0] * (N+1)
    out_t = [0] * (N+1)
    timer = [0]
    stk = [(root, -1, False)]
    while stk:
        v, p, leaving = stk.pop()
        if leaving:
            out_t[v] = timer[0] - 1
        else:
            in_t[v] = timer[0]
            timer[0] += 1
            stk.append((v, p, True))
            for u in adj[v]:
                if u != p:
                    stk.append((u, v, False))
    return in_t, out_t

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

class SegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (2 * n)
    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i >>= 1
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    def query(self, l, r):  # [l, r]
        res = 0
        l += self.n; r += self.n + 1
        while l < r:
            if l & 1: res += self.tree[l]; l += 1
            if r & 1: r -= 1; res += self.tree[r]
            l >>= 1; r >>= 1
        return res

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

    # DFS: sz, parent, heavy child
    sz = [1] * (N+1)
    par = [0] * (N+1)
    depth = [0] * (N+1)
    heavy = [-1] * (N+1)
    stk = [(1, 0, False)]
    while stk:
        v, p, done = stk.pop()
        if done:
            for u in adj[v]:
                if u != par[v]:
                    sz[v] += sz[u]
                    if heavy[v] == -1 or sz[u] > sz[heavy[v]]:
                        heavy[v] = u
        else:
            par[v] = p
            depth[v] = depth[p] + 1
            stk.append((v, p, True))
            for u in adj[v]:
                if u != p:
                    stk.append((u, v, False))

    # HLD + Euler tour
    in_t = [0] * (N+1)
    out_t = [0] * (N+1)
    head = [0] * (N+1)
    timer = [0]
    stk = [(1, 0, False, 1)]
    while stk:
        v, p, done, h = stk.pop()
        if done:
            out_t[v] = timer[0] - 1
        else:
            head[v] = h
            in_t[v] = timer[0]
            timer[0] += 1
            stk.append((v, p, True, h))
            for u in adj[v]:
                if u != par[v] and u != heavy[v]:
                    stk.append((u, v, False, u))
            if heavy[v] != -1:
                stk.append((heavy[v], v, False, h))

    seg = SegTree(N)
    for v in range(1, N+1):
        seg.update(in_t[v], W[v-1])

    def path_query(u, v):
        res = 0
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]:
                u, v = v, u
            res += seg.query(in_t[head[u]], in_t[u])
            u = par[head[u]]
        if depth[u] > depth[v]:
            u, v = v, u
        res += seg.query(in_t[u], in_t[v])
        return res

    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            v, x = int(line[1]), int(line[2])
            seg.update(in_t[v], x)
        elif line[0] == '2':
            v = int(line[1])
            out.append(seg.query(in_t[v], out_t[v]))
        else:
            u, v = int(line[1]), int(line[2])
            out.append(path_query(u, v))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1オイラーツアーとは
DFS中にノードに入った時刻 in[v] と出た時刻 out[v] を記録。部分木 $v$ に含まれる頂点は全て in[v] ≤ in[u] ≤ out[v] を満たす。これでセグメント木の区間 [in[v], out[v]] が部分木に対応。

2セグメント木との組み合わせ
頂点を in 時刻の順にセグメント木に配置。部分木クエリ = 区間和。点更新 = 1頂点の重み変更。各 $O(\log N)$。

3HLDでパスクエリ
重鎖分解でパスを $O(\log N)$ 本の連続区間に分割。各区間をセグメント木で $O(\log N)$ でクエリ。合計 $O(\log^2 N)$。

4HLDの実装詳細
重い子（最大部分木サイズの子）を優先してDFS。これにより同じ重鎖の頂点が連続した in 時刻を持つ。

5非再帰DFSの必要性
Python の再帰上限（デフォルト1000）を超えないよう、iterative DFS に変換する。sys.setrecursionlimit よりも安全。

計算量

構築（DFS×2 + SegTree初期化）: $O(N)$
点更新: $O(\log N)$
部分木クエリ: $O(\log N)$
パスクエリ（HLD）: $O(\log^2 N)$
全体: $O((N + Q) \log^2 N)$

よくあるミス

ミス	原因	正しい書き方
部分木 out が小さすぎる	DFSの順序・スタック処理	`out[v]` は退出時の `timer-1`
パスクエリで頂点を二重カウント	LCA 含む区間の扱い	head が同じになったら1回のみ加算
HLD の head 設定ミス	重い子以外のheadを引き継ぐ	非重鎖の先頭は自分自身が head
N≥10^5 の再帰DFS	Pythonのスタック上限	iterative DFSに変換

次のステップ

発展問題: 辺重みのパスクエリ（辺を子頂点に対応付け）
応用: 部分木最大値・GCDクエリ、辺削除・追加のオンライン版
類題: AtCoder Library の lazysegtree を使った実装

自己評価

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