Day 021-Q1 | 木の同型判定（AHU Algorithm）

問題

$N$ 頂点の根付き木 $T_1$ と $M$ 頂点の根付き木 $T_2$ が与えられる。$T_1$ と $T_2$ が同型（Isomorphic）であるか判定し、同型ならば頂点の対応（写像）を1つ出力せよ。

根付き木の同型とは、根を根に対応させる全単射 $f: V(T_1) \to V(T_2)$ が存在し、$(u, v) \in E(T_1) \iff (f(u), f(v)) \in E(T_2)$ を満たすことである。

入力形式

N
p_2 p_3 ... p_N   (T1 の各頂点の親、頂点1が根)
M
q_2 q_3 ... q_M   (T2 の各頂点の親、頂点1が根)

制約

$2 \leq N, M \leq 2 \times 10^5$

$1 \leq p_i < i$（$T_1$ の親）

$1 \leq q_j < j$（$T_2$ の親）

入出力例

入力例 1

7
1 1 2 2 3 3
7
1 1 2 2 3 3

出力例 1

入力例 2

出力例 2

No

ヒント (段階的開示)

ヒント1: 方向性

木の同型判定は「ハッシュ」を用いて子孫の構造を圧縮する。同じ構造の部分木には同じハッシュを割り当てる。

ヒント2: アプローチ

AHU (Aho-Hopcroft-Ullman) アルゴリズム: 後順DFSで各頂点の子のハッシュ集合をソートしてマッピングする。同一ハッシュ値の子同士が対応頂点候補になる。

ヒント3: 誘導

from collections import defaultdict

def tree_hash(children, root):
    hash_map = {}  # tuple -> int
    vertex_hash = {}

    def dfs(v):
        child_hashes = sorted(dfs(c) for c in children[v])
        key = tuple(child_hashes)
        if key not in hash_map:
            hash_map[key] = len(hash_map)
        vertex_hash[v] = hash_map[key]
        return hash_map[key]

    dfs(root)
    return vertex_hash, hash_map

模範解答 (Python)

import sys
from collections import defaultdict
sys.setrecursionlimit(300000)

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    pos = 0

    N = data[pos]; pos += 1
    ch1 = defaultdict(list)
    for i in range(2, N+1):
        p = data[pos]; pos += 1
        ch1[p].append(i)

    M = data[pos]; pos += 1
    ch2 = defaultdict(list)
    for j in range(2, M+1):
        q = data[pos]; pos += 1
        ch2[q].append(j)

    if N != M:
        print("No")
        return

    # グローバルハッシュ辞書（両木共有）
    hash_map = {}

    h1 = {}
    def dfs1(v):
        child_hashes = sorted(dfs1(c) for c in ch1[v])
        key = tuple(child_hashes)
        if key not in hash_map:
            hash_map[key] = len(hash_map)
        h1[v] = hash_map[key]
        return h1[v]

    h2 = {}
    def dfs2(v):
        child_hashes = sorted(dfs2(c) for c in ch2[v])
        key = tuple(child_hashes)
        if key not in hash_map:
            hash_map[key] = len(hash_map)
        h2[v] = hash_map[key]
        return h2[v]

    dfs1(1)
    dfs2(1)

    if h1[1] != h2[1]:
        print("No")
        return

    # 写像の構築
    mapping = {}

    def build_mapping(v1, v2):
        mapping[v1] = v2
        groups1 = defaultdict(list)
        for c in ch1[v1]:
            groups1[h1[c]].append(c)
        groups2 = defaultdict(list)
        for c in ch2[v2]:
            groups2[h2[c]].append(c)

        for hval in groups1:
            if hval not in groups2 or len(groups1[hval]) != len(groups2[hval]):
                return False
            for c1, c2 in zip(groups1[hval], groups2[hval]):
                if not build_mapping(c1, c2):
                    return False
        return True

    if build_mapping(1, 1):
        print("Yes")
        for v1 in range(1, N+1):
            print(v1, mapping[v1])
    else:
        print("No")

solve()

Step-by-Step 解説

1AHUアルゴリズムの核心
後順DFS（葉から根へ）で各頂点に「構造ハッシュ」を割り当てる。葉のハッシュは全て同じ () → 0。内部ノードは子のハッシュをソートしたタプルをキーとする。

2両木で共通のハッシュ辞書を使う
同じ構造が $T_1$ と $T_2$ 両方に現れても同一の整数が割り当てられる。これにより根のハッシュが一致 ⟺ 木が同型。

3写像の復元
対応頂点 $(v_1, v_2)$ を再帰的に処理。子をハッシュ値でグループ化して、同一ハッシュグループ内でペアリングする（順序は任意でよい）。

4計算量
ハッシュ計算: $O(N \log N)$（子のソートのため）。写像構築: $O(N \log N)$。合計: $O(N \log N)$。

よくあるミス

ミス	原因	正しい書き方
子のハッシュをソートせずタプル化	順序依存になる	`sorted(...)` 必須
両木で別々のhash_mapを使う	異なる番号が割り当たり比較不能	共通のglobal hash_mapを使う
再帰深度超過	$N \leq 2 \times 10^5$ の場合	`sys.setrecursionlimit` + 反復DFSに変換

Day 021-Q1 — 木の同型判定（AHU Algorithm）

問題