Day 051-Q3 | 木の同型判定正準形（Tree Canonical Form + Hashing）

問題

$N$ 頂点の根付き木 $T_1$、$T_2$（根は頂点 1）が与えられる。$Q$ 個のクエリを処理せよ。

クエリ型 1: 1 v w — $T_1$ の頂点 $v$ の部分木と $T_2$ の頂点 $w$ の部分木が同型かどうかを YES/NO で答えよ
クエリ型 2: 2 v c — $T_1$ の頂点 $v$ の子 $c$ への辺を削除し、$c$ を $T_1$ の根の直接の子として付け替える

制約

パラメータ	範囲
$N$	$1 \le N \le 2 \times 10^5$
$Q$	$1 \le Q \le 10^5$
型2クエリ回数	$O(\log N)$ 回以下（保証）
時間制限	4秒

入出力例

入力例 1

出力例 1

YES
YES

T1, T2 は同じ構造。頂点 2 の部分木同士、頂点 5（葉）同士いずれも同型。

概念図: 正準形ハッシュの計算

ヒント（段階的開示）

ヒント1: 方向性

根付き木の同型判定は「正準形（Canonical Form）ハッシュ」で解決できる。AHU アルゴリズム：葉から根方向に、子ハッシュのソート済みタプルを辞書でインターン化して整数 ID を割り当てる。同一 ID = 同型。

ヒント2: アプローチ

hash[葉] = 1（定数）
hash[v] = intern(tuple(sorted(hash[c] for c in children[v])))
intern: タプル → 整数ID の辞書（初出なら新IDを発行）
型2（辺付け替え）: 変更箇所から根まで再計算 $O(\text{depth})$

ヒント3: 反復 DFS でのハッシュ計算

hash_map = {}; hash_counter = [2]

def get_hash(child_hash_tuple):
    if child_hash_tuple not in hash_map:
        hash_map[child_hash_tuple] = hash_counter[0]
        hash_counter[0] += 1
    return hash_map[child_hash_tuple]

# 反復後順 DFS
stack = [(root, -1)]
while stack:
    v, par = stack.pop()
    order.append(v); parent[v] = par
    for u in adj[v]:
        if u != par: stack.append((u, v))

for v in reversed(order):
    children = [u for u in adj[v] if u != parent[v]]
    h[v] = get_hash(tuple(sorted(h[c] for c in children)))

模範解答 (Python)

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

hash_map = {}; hash_counter = [2]
def get_hash(tup):
    if tup not in hash_map:
        hash_map[tup] = hash_counter[0]; hash_counter[0] += 1
    return hash_map[tup]

def build(n, edges):
    adj = defaultdict(list)
    for u,v in edges:
        adj[u].append(v); adj[v].append(u)
    return adj

def compute_hashes(n, adj, root=1):
    h = [0]*(n+1); parent = [-1]*(n+1); order = []
    stack = [(root,-1)]
    while stack:
        v,par = stack.pop(); parent[v]=par; order.append(v)
        for u in adj[v]:
            if u!=par: stack.append((u,v))
    for v in reversed(order):
        children = [u for u in adj[v] if u!=parent[v]]
        h[v] = get_hash(tuple(sorted(h[c] for c in children)))
    return h, parent

def recompute_up(v, adj, h, parent):
    cur = v
    while cur != -1:
        children = [u for u in adj[cur] if u!=parent[cur]]
        h[cur] = get_hash(tuple(sorted(h[c] for c in children)))
        cur = parent[cur]

def solve():
    N, Q = map(int, input().split())
    e1 = [tuple(map(int,input().split())) for _ in range(N-1)]
    e2 = [tuple(map(int,input().split())) for _ in range(N-1)]
    adj1 = build(N,e1); adj2 = build(N,e2)
    h1,par1 = compute_hashes(N,adj1)
    h2,par2 = compute_hashes(N,adj2)
    out = []
    for _ in range(Q):
        line = list(map(int,input().split()))
        if line[0]==1:
            out.append('YES' if h1[line[1]]==h2[line[2]] else 'NO')
        else:
            v,c = line[1],line[2]
            adj1[v].remove(c); adj1[c].remove(v)
            adj1[1].append(c); adj1[c].append(1)
            par1[c] = 1
            recompute_up(v,adj1,h1,par1)
            children_root = [u for u in adj1[1] if u!=par1[1]]
            h1[1] = get_hash(tuple(sorted(h1[u] for u in children_root)))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1正準形ハッシュの定義
$hash(\text{葉}) = 1$、$hash(v) = \text{intern}(\text{sort}([hash(c) \mid c \in \text{children}(v)]))$。子の順序を無視して同型を判定。

2インターニング（辞書によるID付与）
ソート済みタプル → 整数ID の辞書 hash_map。初出のタプルに連番IDを発行。等価な部分木は必ず同じIDを持つ。

3反復後順 DFS
スタックで DFS を反復実装し order を記録。reversed(order)（葉から根の順）でハッシュを計算。$N = 2 \times 10^5$ の再帰はスタックオーバーフロー必至。

4辺付け替え後の再計算
辺を削除・追加した頂点 $v$ から根まで遡り、各頂点のハッシュを再計算。型2クエリが $O(\log N)$ 回なら全体 $O(N + Q \log N)$。

計算量

前処理（ハッシュ全計算）: $O(N \log N)$（ソートによる）
同型クエリ（型1）: $O(1)$
辺付け替え（型2）: $O(\text{depth})$ — 保証により $O(N)$ ワースト、$O(\log N)$ 平均
全体: $O(N \log N + Q)$
空間: $O(N)$

よくあるミス

ミス	原因	正しい書き方
子ハッシュをソートしない	子の順序に依存した比較になり同型を見逃す	`tuple(sorted(...))`
辺付け替え後の再計算漏れ	古いハッシュで誤判定	`recompute_up` を呼ぶ
再帰 DFS でスタックオーバーフロー	$N=2 \times 10^5$ で深さが最大 $N$	反復 DFS に変換
根のハッシュ再計算忘れ	型2で根の子が変わったのに更新しない	型2後に根のハッシュも再計算

次のステップ

発展問題: 根なし木の同型判定（重心を根として正準形を計算）
関連: AHU アルゴリズムによる $O(N)$ 木の同型判定（ランク圧縮）
応用: フォレスト（複数の木）の同型クラス分類

自己評価

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