ZJOI 2014 訓練：雞腿的花園——二叉樹同構子樹計數

問題描述

給定兩棵二叉樹，求有多少對子樹（一棵來自樹 A，一棵來自樹 B）完全相同。二叉樹相同定義：節點數相同、根節點孩子數相同、對應子樹遞歸相同、且左右孩子有序（即左子樹對應左子樹，右對應右）。

核心思路：樹哈希 / 序列化 + 哈希表計數

對每棵樹的所有節點，計算其子樹的「標準化表示」（哈希值或括號序列化字符串）。相同結構的子樹哈希值相同。統計兩棵樹中每種哈希值的出現次數，答案為 Σ cntA[h] * cntB[h]。

序列化方法

遞歸序列化：serialize(u) = "(" + serialize(left) + ")" + "(" + serialize(right) + ")"。空節點表示為空串或特殊符號。括號保證結構唯一性。

哈希優化（避免字符串拷貝）

用雙哈希或 64 位隨機哈希：
hash(u) = splitmix64( hash(left) * P1 + hash(right) * P2 + VAL )。
預先生成隨機數映射節點值（本題節點無值，只比結構，可用固定常數）。

算法流程

1. 對樹 A 所有節點計算子樹哈希，統計 cntA[h]++。
2. 對樹 B 同理統計 cntB[h]++。
3. 遍歷 cntA，累加 cntA[h] * cntB[h]。

代碼框架

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

struct Node { int left, right; };
vector treeA, treeB;
unordered_map cntA, cntB;
const ull P1 = 91138233, P2 = 972663749;

ull splitmix64(ull x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

ull dfsA(int u) {
    if (u == 0) return 0; // 空節點哈希為 0
    ull hL = dfsA(treeA[u].left);
    ull hR = dfsA(treeA[u].right);
    ull h = splitmix64(hL * P1 + hR * P2 + 12345);
    cntA[h]++;
    return h;
}

ull dfsB(int u) {
    if (u == 0) return 0;
    ull hL = dfsB(treeB[u].left);
    ull hR = dfsB(treeB[u].right);
    ull h = splitmix64(hL * P1 + hR * P2 + 12345);
    cntB[h]++;
    return h;
}

int main() {
    // 讀入兩棵樹構建 treeA, treeB（略）
    dfsA(1); dfsB(1);
    long long ans = 0;
    for (auto &[h, c] : cntA) if (cntB.count(h)) ans += 1LL * c * cntB[h];
    cout << ans << '\n';
    return 0;
}

關鍵點

• 有序二叉樹：左右孩子不可交換，序列化/哈希須區分左右。
• 空節點統一哈希值（如 0），保證葉子節點哈希正確。
• 用 splitmix64 或 std::hash 組合，極低碰撞概率；極高要求可用雙模哈希或字符串序列化作驗證。
• 時間 O(N+M)，空間 O(N+M)。

注意

原題輸入格式未給出，上述代碼假設標準樹輸入（節點數 + 左右孩子索引）。實際比賽中需按題目具體格式解析。