木の同型判定

葉から順に、各頂点に「子の番号をソートして並べた組」に対応する番号を振ります（AHU アルゴリズム）。組から番号への対応は辞書で持つので、ハッシュと違って衝突の心配がありません。根のない木どうしは、重心（1 個か 2 個）を根にして比べます。再帰は使いません。

• subtree_ids(g, root, table): 木の隣接リスト g[v] = [to, ...] を root を根として見て、各頂点を根とする部分木の形の番号のリストを返す。2 つの部分木が根付き木として同型なとき、またそのときに限り番号が等しい。 $O(N \log N)$
• table: 組から番号への辞書。いくつかの木の番号を比べるときは、同じ辞書を渡す（省略すると新しい辞書を使う）
• centroids(g): 木の重心のリスト（1 個か 2 個）。 $O(N)$
• isomorphic(g1, g2): 根のない木 g1, g2 が同型か。 $O(N \log N)$

例（部分木の形が何種類あるか）:

ans = len(set(subtree_ids(g)))

コード

def subtree_ids(g, root=0, table=None):
    # 各頂点を根とする部分木の形に番号を振ったリスト（根付き木として同型なら同じ番号）
    # いくつかの木の番号を比べるときは、同じ辞書 table を渡す
    if table is None:
        table = {}
    n = len(g)
    par = [-1] * n
    order = [root]
    for v in order:
        for to in g[v]:
            if to != par[v]:
                par[to] = v
                order.append(to)
    ch = [[] for _ in range(n)]
    res = [0] * n
    for v in reversed(order):
        key = tuple(sorted(ch[v]))
        if key not in table:
            table[key] = len(table)
        res[v] = table[key]
        if v != root:
            ch[par[v]].append(res[v])
    return res


def centroids(g):
    # 木の重心（1 個か 2 個）のリスト
    n = len(g)
    par = [-1] * n
    order = [0]
    for v in order:
        for to in g[v]:
            if to != par[v]:
                par[to] = v
                order.append(to)
    size = [1] * n
    for v in reversed(order[1:]):
        size[par[v]] += size[v]
    res = []
    for v in range(n):
        mx = n - size[v]
        for to in g[v]:
            if to != par[v]:
                mx = max(mx, size[to])
        if 2 * mx <= n:
            res.append(v)
    return res


def isomorphic(g1, g2):
    # 根のない木 g1, g2 が同型か
    if len(g1) != len(g2):
        return False
    c1, c2 = centroids(g1), centroids(g2)
    if len(c1) != len(c2):
        return False
    table = {}
    x = subtree_ids(g1, c1[0], table)[c1[0]]
    return any(subtree_ids(g2, c, table)[c] == x for c in c2)