思路与算法

对每个节点递归统计子树大小和合法序列数。兄弟只有各自根的先后固定，其后代可以交错。按孩子喜爱顺序从后向前合并；已有rest个后续孩子节点，当前孩子大小s，当前孩子根必须放在合并序列首位，余下s-1个与rest个保持各自顺序地穿插，有C(s+rest-1,rest)种。乘当前孩子内部方案并累加大小，最后前置父节点。

正确性说明

归纳假设各子树内部方案精确。合并时固定当前孩子根先于后续兄弟根；其余元素只受本子树内部顺序约束，与后续序列的交错位置可任取且唯一恢复。二项式正好数全部交错，无额外的子树连续限制。逐孩子、逐节点归纳得到全树答案。

复杂度

每组Pascal组合表初始化与填充O(N²)，DFS和所有孩子合并O(N)，总O(N²)时间、O(N²)空间；递归栈最坏O(N)。

易错点

孩子顺序按输入，不能排序编号。兄弟根先后不意味着一整个子树都须连续。根恒1，N=1有一种方案。组合数模10007。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n), C(n + 1, vector<int>(n + 1));
        for (int i = 0; i < n; i++) {
            int k;
            cin >> k;
            g[i].resize(k);
            for (int &v : g[i]) {
                cin >> v;
                --v;
            }
        }
        for (int i = 0; i <= n; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
        vector<int> sz(n), ways(n);
        function<void(int)> dfs = [&](int u) {
            int rest = 0;
            long long ans = 1;
            for (int j = (int)g[u].size() - 1; j >= 0; j--) {
                int v = g[u][j];
                dfs(v);
                ans = ans * ways[v] % MOD * C[sz[v] + rest - 1][rest] % MOD;
                rest += sz[v];
            }
            sz[u] = rest + 1;
            ways[u] = ans;
        };
        dfs(0);
        cout << ways[0] << '\n';
    }
}