题解 | #至至子的公司排队#

树形 $\text{DP}\backslash text\{DP\}$。

设以 $uu$ 为根的子树的答案为 $f_{u}f\_u$，考虑如何合并两棵子树的答案。

假如我们有两个合法排队序列 $A,BA,B$，长分别为 $n,mn,m$，那么将这两个序列归并为 $CC$，若在 $CC$ 中 $A,BA,B$ 中元素的相对顺序没有变化，那么 $CC$ 也是合法的排队序列。

这个过程可以看作 $nn$ 个相同小球放入 $m+1m+1$ 个不同的盒子，方案数为 $\left(\genfrac{}{}{0px}{}{n+1+m-1}{m+1-1}\right)=\left(\genfrac{}{}{0px}{}{n+m}{m}\right)\backslash binom\{n+1+m-1\}\{m+1-1\}=\backslash binom\{n+m\}\{m\}$。

对于两颗子树 $u,vu,v$ 及父亲 $ff$，由于 $ff$ 一定在每个序列的最前面，所以不产生贡献，故 $f_f=f_u\times f_v\times \left(\genfrac{}{}{0px}{}{{\mathrm{size}}_{}+{\mathrm{size}}_{}}{{\mathrm{size}}_{}}\right)f\_f=f\_u\backslash times\; f\_v\backslash times\backslash binom\{\backslash operatorname\{size\}\_u+\backslash operatorname\{size\}\_v\}\{\backslash operatorname\{size\}\_v\}$。

由于题目给出的是一个森林，我们直接开一个超级父亲作为所有树的根的父亲，同理也不会对答案产生影响。

由于 $\mathrm{size}\backslash operatorname\{size\}$ 的大小是 $O(n)O(n)$ 的，可以直接花费 $O(n+\log p)O(n+\backslash log\; p)$ 的时间预处理阶乘和逆元，公式算组合数即可。

总时间复杂度 $O(n+\log p)O(n+\backslash log\; p)$。

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <vector>

using namespace std;

const int Mod = 1e9 + 7;
const int N = 5e5 + 225;

vector< int >G[ N ];
# define pb push_back

int n , C = 1;

typedef long long ll;
ll F[ N ] , siz[ N ];

ll Quick_Pow( ll x , ll y ){
    ll res = 1;
    while( y ){
        if( y & 1 ) res = res * x % Mod;
        y >>= 1 , x = x * x % Mod;
    }
    return res;
}

ll Fac[ N ] , Inv[ N ];
void Init(){
    Fac[ 0 ] = 1;
    for( int i = 1 ; i <= C ; i ++ ) Fac[ i ] = Fac[ i - 1 ] * i % Mod;
    Inv[ C ] = Quick_Pow( Fac[ C ] , Mod - 2 );
    for( int i = C - 1 ; i >= 1 ; i -- ) Inv[ i ] = Inv[ i + 1 ] * ( i + 1 ) % Mod;
}

ll Binom( ll n , ll m ){
    if( m > n ) return 0;
    return ( Fac[ n ] * Inv[ m ] % Mod ) * Inv[ n - m ] % Mod;
}

void DFS( int u ){
    siz[ u ] = F[ u ] = 1;
    ll s = 0;
    for( int v : G[ u ] ){
        DFS( v ) , siz[ u ] += siz[ v ];
        if( ! s ) F[ u ] = F[ v ];
        else F[ u ] = ( F[ u ] * F[ v ] % Mod ) * Binom( s + siz[ v ] , siz[ v ] ) % Mod;
        s += siz[ v ];
    }
}

void Input(){
    scanf( "%d" , & n );
    for( int i = 1 ; i <= n ; i ++ ){
        int c;
        scanf( "%d" , & c );
        G[ 1 ] . pb( C + 1 );
        for( int i = 2 ; i <= c ; i ++ ){
            int f;
            scanf( "%d" , & f );
            f += C;
            G[ f ] . pb( i + C );
        }
        C += c;
    }
}

int main(){
    Input();
    Init();
    DFS( 1 );
    printf( "%lld\n" , F[ 1 ] );
    return 0;
}