HDU 5379 Mahjong Tree：樹形構造計數

題目大意

給定一棵 n 個節點的樹（根為 1），需將 1~n 的標號分配給節點，滿足：(1) 每個節點的所有子節點標號連續；(2) 任意子樹的標號連續。求方案數模 1e9+7。

關鍵觀察

• 非葉子節點最多兩個，且其標號必須是所在連續區間的端點（最大值或最小值）。
• 葉子節點在區間內可任意排列，貢獻階乘。
• 對於一個非葉子節點，有 2 種選擇（取區間左端或右端），其葉子孩子有 k! 種排列，非葉子孩子遞歸計算。

算法

DFS 遍歷樹，統計每個節點的葉子孩子數 son1 和非葉子孩子數 son2。若 son2 > 2 則無解。答案累乘 2 (若 son2>0) * son1!。根節點若有非葉子孩子，再乘 2。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, MAXN = 100005;
vector<int> g[MAXN];
int fact[MAXN];

int dfs(int u, int fa) {
    long long ans = 1;
    int son1 = 0, son2 = 0;
    for (int v : g[u]) if (v != fa) {
        int res = dfs(v, u);
        if (!res) return 0;
        ans = ans * res % MOD;
        if (g[v].size() == 1) son1++;
        else son2++;
    }
    if (son2 > 2) return 0;
    if (son2) ans = ans * 2 % MOD;
    ans = ans * fact[son1] % MOD;
    return ans;
}

int main() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = 1LL * fact[i-1] * i % MOD;
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v); g[v].push_back(u);
        }
        int ans = dfs(1, 0);
        if (g[1].size() > 1) ans = 2LL * ans % MOD; // 根節點特殊處理
        printf("Case #%d: %d\n", cs, ans);
    }
    return 0;
}