Day 045-Q1 — 木の平方根分解（Sqrt Decomposition on Trees）

2026-05-29 赤色 Master / Phase 8+ ★★★★★★★★★ Sqrt Decomp + 木の祖先クエリ + XOR

問題

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

  • 1 v x：頂点 $v$ の値を $x$ に更新する
  • 2 v k：頂点 $v$ の祖先（深さが $\text{depth}(v) - k \cdot B$ 以上、$B = \lfloor\sqrt{N}\rfloor$）の XOR を求める

制約

$1 \le N, Q \le 2 \times 10^5$
$1 \le a_v \le 10^9$
$1 \le x \le 10^9$
$1 \le k \le \lfloor\sqrt{N}\rfloor$
時間制限: 2秒

入出力例

入力例 1

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

出力例 1

6
7
3

概念図: ブロック分割による祖先XOR

1(root) 2 3 4 5 6 7 Block 1 (depth 1) Block 2 (depth 2) B = ⌊√N⌋ ごとに祖先をブロック化。各頂点が「B個上の祖先」への参照と、ブロック内XOR集計値を保持。 クエリ: ブロック単位でXOR累積 O(√N) + 端数をナイーブに辿る。更新: 影響ブロックを再計算。

ヒント（段階的開示）

ヒント1: 方向性
木全体を「ブロック」に分割する考え方があります。$B = \lfloor\sqrt{N}\rfloor$ 個の祖先ごとに集約値を保持するとクエリを高速化できます。
ヒント2: アプローチ
  • 各頂点 $v$ に対して「$B$ 個上の祖先」への参照 anc_B[v] を事前計算
  • 各頂点のブロック内XOR累積値 prefix_xor[v] を保持
  • クエリ: ブロック境界までの端数をナイーブに辿り、残りはブロック単位で累積XOR
ヒント3: 実装骨格 
B = isqrt(N)
# 各頂点のB個上の祖先を事前計算 O(N*B) = O(N√N)
for v in BFS_order:
    u = v
    for _ in range(B):
        u = parent[u]; if u==0: break
    anc_B[v] = u
    prefix_xor[v] = XOR(a[v], a[parent[v]], ..., a[child_of_anc_B])

# クエリ処理
def query(v, k):  # k*B個上の祖先までのXOR
    result, cur = 0, v
    for _ in range(k):
        result ^= prefix_xor[cur]
        cur = anc_B[cur]
    return result

模範解答 (Python)

import sys
from collections import deque
from math import isqrt

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # 1-indexed
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    if N > 1:
        p = list(map(int, input().split()))
        for i in range(2, N + 1):
            parent[i] = p[i - 2]
            children[p[i-2]].append(i)
    else:
        input()

    B = max(1, isqrt(N))
    depth = [0] * (N + 1)
    anc_B = [0] * (N + 1)
    prefix_xor = [0] * (N + 1)

    order = []
    q = deque([1])
    while q:
        v = q.popleft()
        order.append(v)
        for c in children[v]:
            depth[c] = depth[v] + 1
            q.append(c)

    for v in order:
        u = v
        for _ in range(B):
            u = parent[u]
            if u == 0:
                break
        anc_B[v] = u
        xr = 0
        u = v
        for _ in range(B):
            if u == 0:
                break
            xr ^= a[u]
            u = parent[u]
        prefix_xor[v] = xr

    def query_xor(v, k):
        result = 0
        cur = v
        steps = k * B
        while steps >= B and anc_B[cur] != 0:
            result ^= prefix_xor[cur]
            cur = anc_B[cur]
            steps -= B
        for _ in range(steps):
            if cur == 0:
                break
            result ^= a[cur]
            cur = parent[cur]
        return result

    def update(v, x):
        a[v] = x
        bfs_q = deque([(v, 0)])
        while bfs_q:
            u, d = bfs_q.popleft()
            xr = 0
            w = u
            for _ in range(B):
                if w == 0:
                    break
                xr ^= a[w]
                w = parent[w]
            prefix_xor[u] = xr
            if d < B:
                for c in children[u]:
                    bfs_q.append((c, d + 1))

    results = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            update(line[1], line[2])
        else:
            results.append(query_xor(line[1], line[2]))

    print('\n'.join(map(str, results)))

main()

Step-by-Step 解説

1平方根分解の設計
$B = \lfloor\sqrt{N}\rfloor$ を単位として祖先チェーンをブロック化する。各頂点は「$B$ 個上の祖先」ポインタとブロック内XOR集計値を持つ。
2前処理 O(N√N)
BFSで浅い順に全頂点を処理。各頂点について $B$ ステップ上の祖先を辿りながら XOR を集積する。
3クエリ処理 O(√N)
ブロック単位で `anc_B` ポインタをたどりXORを累積 → 残りの端数をナイーブに辿る。
4更新処理
更新頂点 $v$ の子孫で「ブロック内に $v$ を含む」頂点の `prefix_xor` を再計算。BFSで深さ $B$ までの子孫を再計算する。
5計算量
前処理: $O(N\sqrt{N})$、クエリ: $O(\sqrt{N})$、更新: $O(N)$ 最悪（線形木の場合）、平均的に $O(\sqrt{N})$。

計算量

前処理: $O(N\sqrt{N})$
クエリ: $O(\sqrt{N})$ per query
更新: $O(N)$ 最悪、$O(B \cdot \text{branch\_factor})$ 平均
空間: $O(N)$

よくあるミス

ミス原因正しい書き方
anc_B[v] が 0 を考慮しない根より上は存在しないif anc_B[cur] == 0: break
prefix_xor の更新範囲が不足子孫のブロックを見逃すBFSで深さBまでの子孫全てを更新
1-indexed/0-indexed の混在配列添字バグ入力時に1-indexedに統一
XOR 初期値を 0 にしない誤った値から累積が始まるresult = 0 で初期化

次のステップ

  • 発展問題: 木の平方根分解で「部分木内のXOR最大値クエリ」を $O(\sqrt{N})$ で処理する
  • 類題: 重心分解を使った木のパスクエリ
  • 応用: Heavy-Light Decompositionとの比較・使い分け

自己評価