Day 065-Q2 | 木の平方根分解 + パスクエリ（Tree Block Decomposition）

問題

$N$ 頂点の根付き木（根 = 1）が与えられる。各頂点 $v$ には初期値 $a_v$ が付与されている。以下の $Q$ クエリを処理せよ：

update v x : 頂点 $v$ の値を $x$ に変更する。
path u v : $u$-$v$ パス上の全頂点値の 総 XOR を出力する（LCA を含む）。

制約

パラメータ	範囲
$N, Q$	$1 \le N, Q \le 10^5$
$a_v$	$0 \le a_v \le 10^9$
クエリ	`update v x` または `path u v`

入出力例

入力例 1

7 4
1 2 4 8 16 32 64
1 1 2 2 3 3
update 4 5
path 4 5
path 6 7
path 4 7

出力例 1

7
96
85

path 4 5: LCA=2, 経路4→2→5, XOR=5^2^16=7 | path 6 7: LCA=3, XOR=32^4^64=96

概念図: root_xor を使ったパス XOR 計算

ヒント（段階的開示）

ヒント1: 方向性

root_xor[v] = 根から $v$ までのパス上の全頂点値の XOR（$v$ 自身を含む）を前計算する。パスの XOR は root_xor[u] ^ root_xor[v] ^ a[LCA(u,v)] で求められる（LCA が2回カウントされキャンセルされるため、1回分を追加）。

ヒント2: update の実装

頂点 $v$ の値が old → new に変わるとき、差分 diff = old ^ new を $v$ の部分木内の全頂点 $u$ の root_xor[u] に XOR する。部分木の範囲は Euler Tour の区間 [tin[v], tout[v]] で特定できる。

ヒント3: LCA の実装骨格

# Binary Lifting LCA
LOG = 17
up = [[0]*(N+1) for _ in range(LOG)]
up[0] = parent_list
for k in range(1, LOG):
    for v in range(1, N+1):
        up[k][v] = up[k-1][up[k-1][v]]

def lca(u, v):
    if depth[u] < depth[v]: u, v = v, u
    # 深さを揃える
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if (diff >> k) & 1: u = up[k][u]
    if u == v: return u
    # 一緒に上がる
    for k in range(LOG-1, -1, -1):
        if up[k][u] != up[k][v]:
            u = up[k][u]; v = up[k][v]
    return up[0][u]

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def solve():
    N, Q = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    par = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    if N > 1:
        ps = list(map(int, input().split()))
        for i, p in enumerate(ps, 2):
            par[i] = p
            children[p].append(i)

    # BFSで深さ・root_xorを計算
    depth = [0] * (N + 1)
    root_xor = [0] * (N + 1)
    bfs_order = []
    q = deque([1])
    root_xor[1] = a[1]
    visited = [False] * (N + 1)
    visited[1] = True
    while q:
        v = q.popleft()
        bfs_order.append(v)
        for u in children[v]:
            depth[u] = depth[v] + 1
            root_xor[u] = root_xor[v] ^ a[u]
            visited[u] = True
            q.append(u)

    # Euler Tour (iterative DFS)
    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    timer = [0]
    stack = [(1, False)]
    while stack:
        v, leaving = stack.pop()
        if leaving:
            tout[v] = timer[0]; timer[0] += 1
        else:
            tin[v] = timer[0]; timer[0] += 1
            stack.append((v, True))
            for u in reversed(children[v]):
                stack.append((u, False))

    euler_order = sorted(range(1, N+1), key=lambda v: tin[v])

    # Binary Lifting for LCA
    LOG = 17
    up = [[0] * (N + 1) for _ in range(LOG)]
    up[0][1] = 1
    for v in range(2, N + 1):
        up[0][v] = par[v]
    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]

    def lca(u, v):
        if depth[u] < depth[v]: u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1: u = up[k][u]
        if u == v: return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]; v = up[k][v]
        return up[0][u]

    def path_xor(u, v):
        l = lca(u, v)
        return root_xor[u] ^ root_xor[v] ^ a[l]

    def update(v, x):
        diff = a[v] ^ x
        a[v] = x
        lo, hi = tin[v], tout[v]
        for u in euler_order:
            if lo <= tin[u] and tout[u] <= hi:
                root_xor[u] ^= diff

    out = []
    for _ in range(Q):
        parts = input().split()
        if parts[0] == 'update':
            update(int(parts[1]), int(parts[2]))
        else:
            u, v = int(parts[1]), int(parts[2])
            out.append(str(path_xor(u, v)))

    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: root_xor の管理

root_xor[v] = 根から $v$ までのパス上全頂点値の XOR。BFS で $O(N)$ で計算。

Step 2: パス XOR の公式

$u$-$v$ パスを root_xor で表すと：
root_xor[u] ^ root_xor[v] には根から LCA までのパスが2回（キャンセル）、$u$ と $v$ が各1回含まれる。LCA 自体は2回入るのでキャンセルされてしまうため、^ a[LCA] で1回追加する。

Step 3: update の部分木伝播

Euler Tour で各頂点の tin[v]（入時刻）と tout[v]（退時刻）を記録。$v$ の部分木は tin[v] <= tin[u] and tout[u] <= tout[v] で特定できる。差分 diff = old ^ new を全部分木頂点に XOR する。

Step 4: 計算量

処理	計算量
前処理（BFS + Euler Tour + Binary Lifting）	$O(N \log N)$
path クエリ	$O(\log N)$
update（ナイーブ部分木スキャン）	$O(N)$
update（平方根分解適用時）	$O(\sqrt{N})$

よくあるミス

ミス	原因	正しい書き方
LCA の `u, u = ...` タイポ	変数名のコピーミス	`u = up[k][u]; v = up[k][v]` を別行で
`path_xor` で `a[LCA]` を除く	公式の誤解	LCA は2回キャンセルされるため1回追加 `^ a[l]`
Euler Tour の tout 範囲誤り	tout に退出時刻でなく入時刻を使う	`tout[u] <= tout[v]`（親の退出時刻以下）

次のステップ

発展問題: update の対象をパス上の全頂点への一括加算（パス加算クエリ）に拡張せよ。HLD + 遅延セグメント木で $O(\log^2 N)$ または Euler Tour + セグメント木で対応する。

自己評価

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