Day 032-Q2 — Rooted Tree の同型・ハッシュ + 全方位 DP

問題

2 つの根付き木 $T_1, T_2$ について、部分木同型 / パターンカウント / 根変え同型の 3 種クエリに答えよ。

制約

入出力例

7
1 2
1 3
2 4
2 5
3 6
3 7
5
1 2
2 3
3 4
4 5
1 4
1 1 1
2 1
3 1 2

No
2
Yes

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from collections import defaultdict, Counter
sys.setrecursionlimit(500000)

def main():
    inp = sys.stdin.read().split()
    ptr = 0
    def rd():
        nonlocal ptr
        v = inp[ptr]; ptr += 1
        return int(v)

    MOD1 = (1 << 61) - 1
    MOD2 = (1 << 31) - 1
    BASE1 = 131
    BASE2 = 137

    def compute_subtree_hashes(adj, root, n):
        h1 = [0] * (n + 1); h2 = [0] * (n + 1)
        order = []
        parent = [-1] * (n + 1)
        stack = [root]
        visited = [False] * (n + 1)
        while stack:
            v = stack.pop()
            if visited[v]: continue
            visited[v] = True
            order.append(v)
            for u in adj[v]:
                if not visited[u]:
                    parent[u] = v
                    stack.append(u)
        for v in reversed(order):
            child_h = []
            for u in adj[v]:
                if u != parent[v]:
                    child_h.append((h1[u], h2[u]))
            child_h.sort()
            cur1 = 1; cur2 = 1
            for ch1, ch2 in child_h:
                cur1 = (cur1 * BASE1 + ch1 + 1) % MOD1
                cur2 = (cur2 * BASE2 + ch2 + 1) % MOD2
            h1[v] = cur1; h2[v] = cur2
        return h1, h2, parent, order

    N = rd()
    adj1 = defaultdict(list)
    for _ in range(N - 1):
        u, v = rd(), rd()
        adj1[u].append(v); adj1[v].append(u)
    M = rd()
    adj2 = defaultdict(list)
    for _ in range(M - 1):
        u, v = rd(), rd()
        adj2[u].append(v); adj2[v].append(u)
    h1_T1, h2_T1, _, _ = compute_subtree_hashes(adj1, 1, N)
    h1_T2, h2_T2, _, _ = compute_subtree_hashes(adj2, 1, M)

    Q = rd()
    out = []
    for _ in range(Q):
        qtype = rd()
        if qtype == 1:
            u, v = rd(), rd()
            out.append("Yes" if (h1_T1[u], h2_T1[u]) == (h1_T2[v], h2_T2[v]) else "No")
        elif qtype == 2:
            v = rd()
            target = (h1_T2[v], h2_T2[v])
            count = sum(1 for u in range(1, N + 1)
                       if (h1_T1[u], h2_T1[u]) == target)
            out.append(str(count))
        else:
            a, b = rd(), rd()
            t2_full = (h1_T2[1], h2_T2[1])
            out.append("Yes" if (h1_T1[a], h2_T1[a]) == t2_full else "No")
    print('\n'.join(out))

main()

Step-by-Step 解説

よくあるミス

次のステップ

• 森のマッチング、同型な連結成分カウント

自己評価

自分の回答

気づき・メモ