题目

点这里看题目。

给定一棵包含 \(n\) 个结点的树 \(T\)。对于 \(x\in [0,n-1]\cap \mathbb Z\)，求与 \(T\) 恰好有 \(x\) 条边相同的树的有标号无根树个数。对 \(10^9+7\) 取模。

所有数据满足 \(1\le n\le 100\)（原题）或 \(1\le n\le 8000\)（加强版）。

分析

Matrix-tree

我们把这个问题，看作是“对大小为 \(n^{n-2}\) 的有标号无根树集合，按照与 \(T\) 重合的边的数量分类”。

“数树”这个过程可以想到用 Matrix-tree 定理，然而怎么表征“类”这个概念？“类”由“边”确定，“边”的关系是乘法，而最终边组合起来时，“类”的关系是加法，所以我们需要引入形式变元，这样恰好可以将乘法转化为指数上的加法。

所以将 \(T\) 上的边的边权变成 \(x\) 即可。带着 \(x\) 算高斯消元很恼火，但因为最终结果是多项式，所以我们可以预先代入 \(n\) 个值，代入之后再正常地做高斯消元，最后反过来插值即可求出多项式。复杂度为 \(O(n^4)\)。

套结论

这是一个纯组合的想法。

考虑先钦定 \(x\) 条边相同，算出来方案数 \(g_x\)，最后做一个二项式反演即可得到答案。

钦定了 \(x\) 条边之后，图上就会剩下 \(n-x\) 个连通块。此时再计算将它们用 \(n-x-1\) 条边连起来的方案数，就有定理可以介入：

Theorem.

有 \(n(n>1)\) 个连通块，大小分别为 \(s_1,s_2,\dots,s_n\)，结点有标号。

将它们用 \(n-1\) 条边连成一个连通块，总方案数为：

\[\left(\sum_{k=1}^{n}s_k\right)^{n-2}\prod_{k=1}^ns_k \]

---

Proof.

证明方法多样，我知道的即有 矩阵树定理、Prufer 序列构造 和 扩展拉格朗日反演（什么鬼）。这里不再赘述。

很容易想到在原树 \(T\) 上 DP 以计算方案数。我们必须知道断开的边的数量，所以难点在于处理 \(\prod s\)。

考虑这个结构的组合含义：从每个连通块里面选出一个点来的方案数。那么，结合这个组合意义我们就可以列一个 DP：\(f_{u,x,0/1}\) 表示 \(u\) 子树内，断开了 \(x\) 条边之后，\(u\) 所在连通块没有/已经选了一个点出来的方案总数。转移复杂度显然 \(O(n^2)\)。

但是，这里需要树上背包，空间至少需要 \(2n^2\)！有两种解决方案：

1. 照猫画虎，我们注意到 \(x\) 这一维上做的是多项式卷积，所以我们依然可以代入值计算，最后插值。

   所以，拉格朗日插值很重要的一个应用就是，优化卷积运算的空间复杂度。

2. 使用 std :: vector。我们将一个子树的信息合并到其父亲之后即可回收该子树的 DP 数组，所以有效的空间实际上是 \(O(n)\) 的。

   强制回收某 vector 的空间，方法有两种：使用 shrink_to_fit 成员函数，或者让需要清除的对象 .swap( std :: vector<>() )。这样需要清除的对象和临时空对象 swap 之后自然清空，而空对象的生命周期只有这个语句，因此该语句结束后它就会自动析构释放空间。

3. 重链剖分，直接继承重儿子的 vector，然后暴力合并轻儿子的 vector。

代码

这里只有 \(O(n^2)\) 的参考代码。

#include <cstdio>
#include <vector>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 1e9 + 7;
const int MAXN = 8005;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

struct Edge {
    int to, nxt;
} Graph[MAXN << 1];

int f[MAXN], g[MAXN], C[MAXN];

std :: vector<int> dp[MAXN][2];
int tmp[2][MAXN];

int siz[MAXN], heavy[MAXN];
int head[MAXN], cnt = 1;

int N;

inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline int Qkpow( int base, int indx ) {
    int ret = 1;
    while( indx ) {
        if( indx & 1 ) MulEq( ret, base );
        MulEq( base, base ), indx >>= 1;
    }
    return ret;
}

inline void AddEdge( const int &from, const int &to ) {
    Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
    head[from] = cnt;
}

void Init( const int &u, const int &fa ) {
    siz[u] = 1, heavy[u] = 0;
    for( int i = head[u], v ; i ; i = Graph[i].nxt )
        if( ( v = Graph[i].to ) ^ fa ) {
            Init( v, u ), siz[u] += siz[v];
            if( siz[heavy[u]] < siz[v] ) heavy[u] = v;
        }
}

void DFS( const int &u, const int &fa ) {
    siz[u] = 0;
    if( ! heavy[u] ) {
        dp[u][0].push_back( 1 );
        dp[u][1].push_back( 1 );
        return ;
    }
    DFS( heavy[u], u ); 
    siz[u] = siz[heavy[u]] + 1;
    dp[u][0].swap( dp[heavy[u]][0] );
    dp[u][1].swap( dp[heavy[u]][1] );
    // 不断新边
    rep( i, 0, siz[u] - 1 )
        tmp[0][i] = dp[u][0][i],
        tmp[1][i] = Add( dp[u][0][i], dp[u][1][i] );
    // 断新边
    tmp[0][siz[u]] = tmp[1][siz[u]] = 0;
    rep( i, 0, siz[u] - 1 )
        AddEq( tmp[0][i + 1], dp[u][1][i] ),
        AddEq( tmp[1][i + 1], dp[u][1][i] );
    dp[u][0].push_back( 0 );
    dp[u][1].push_back( 0 );
    rep( i, 0, siz[u] ) 
        dp[u][0][i] = tmp[0][i],
        dp[u][1][i] = tmp[1][i];
    for( int i = head[u], v ; i ; i = Graph[i].nxt )
        if( ( v = Graph[i].to ) ^ fa && v ^ heavy[u] ) {
            DFS( v, u );
            rep( j, 0, siz[u] + siz[v] + 1 )
                tmp[0][j] = tmp[1][j] = 0;
            rep( j, 0, siz[u] ) rep( k, 0, siz[v] ) {
                // 不断新边
                AddEq( tmp[0][j + k], Mul( dp[u][0][j], dp[v][0][k] ) );
                AddEq( tmp[1][j + k], Add( Mul( dp[u][1][j], dp[v][0][k] ), Mul( dp[u][0][j], dp[v][1][k] ) ) );
                // 断新边
                AddEq( tmp[0][j + k + 1], Mul( dp[u][0][j], dp[v][1][k] ) );
                AddEq( tmp[1][j + k + 1], Mul( dp[u][1][j], dp[v][1][k] ) );
            }
            // dp[v][0].clear(), dp[v][0].shrink_to_fit();
            // dp[v][1].clear(), dp[v][1].shrink_to_fit();
            dp[v][0].clear(), dp[v][1].clear();
            dp[u][0].resize( siz[u] + siz[v] + 2, 0 );
            dp[u][1].resize( siz[u] + siz[v] + 2, 0 );
            rep( j, 0, siz[u] + siz[v] + 1 ) 
                dp[u][0][j] = tmp[0][j], dp[u][1][j] = tmp[1][j];
            siz[u] += siz[v] + 1;
        }
}

int main() {
    Read( N );
    rep( i, 1, N - 1 ) {
        int u, v; Read( u ), Read( v );
        AddEdge( u, v ), AddEdge( v, u );
    }
    Init( 1, 0 );
    DFS( 1, 0 );
    rep( i, 1, N - 1 )
        f[N - 1 - i] = Mul( Qkpow( N, i - 1 ), dp[1][1][i] );
    f[N - 1] = 1, C[0] = 1;
    rep( i, 0, N - 1 ) {
        rep( j, 0, i ) {
            if( ( i & 1 ) ^ ( j & 1 ) )
                SubEq( g[j], Mul( C[j], f[i] ) );
            else
                AddEq( g[j], Mul( C[j], f[i] ) );
        }
        per( j, i + 1, 1 ) AddEq( C[j], C[j - 1] );
    }
    rep( i, 0, N - 1 ) Write( g[i] ), putchar( " \n"[i == N - 1] );
    return 0;
}