ZROI 3.17 B

我们考虑 恰好进行 $k$ 次这样的操作，就是让你求有多少个树，满足这个树和原来的树重复的边的数量不少于 $n - k - 1$。

考虑 $F[x]$ 表示重复边数量正好是 $x$ 的方案数量，然后这里用到了一个经典（但我不会）的套路，二项式反演（其实就是容斥），也就是说钦定一些边必须是相同的，剩下的边随意连形成的树，

考虑设 $f[x]$ 表示钦定 $x$ 条边必须相同，剩下的边任意连形成的树的个数，那么容斥一下就是：

$$F[x] = f[x] - \sum_{i > x} f[i]{i\choose x}$$

所以我们现在需要计算的就是 $f$ 。

我们考虑钦定 $x$ 条边后，我们相当于是要选出 $n-x$ 个联通块。我们设 $m = n-x$ 也就是联通块数量，首先考虑把联通块看成点，给这些联通块之间连边，形成一个树，这个过程就是一个 prufer 序，方案为 $n^{m-2}$ 。

然后考虑每个联通块实际上的贡献，假设这个联通块连出去的边的度数为 $d$ ，这 $d$ 个边可以是联通块内任意一个点连出去的，如果设这个联通块大小为 $a_i$ ，所以方案有 $a_i^d$ 。但是实际上呢，在 prufer 序里面我们只算了这个联通块内的点出现了 $d-1$ 次后的方案数，所以我们需要给 prufer 序算出的东西乘上 $\prod a_i$。于是式子就是：

$$n^{m-2} \prod a_i$$

而一个非常经典的组合意义告诉我们，$\prod a_i$ 可以看成在每个联通块选择一个点的方案数量。于是我们可以设 $dp[u][k][0/1]$ 表示当前在 $u$ ，它的子树中钦定了 $k - 1$ 个边（也就是分成了 $k$ 个联通块）， $u$ 所在的联通块是否选点的方案数量。

转移可以树形背包类似的转移。

仓老师讲得好！/se

最后。。这题define int longlong 居然比不define 快了300ms。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
using namespace std;
#define int long long
#define MAXN 5006
#define P 1000000007
int n , m;
int dp[MAXN][MAXN][2] , siz[MAXN] , t[MAXN][2];
vector<int> G[MAXN];
void dfs( int u , int fa ) {
    siz[u] = 1;
    dp[u][1][0] = dp[u][1][1] = 1;
    for( int v : G[u] ) if( v != fa ) {
        dfs( v , u );
        for( int i = 1 ; i <= siz[u] + siz[v] ; ++ i ) t[i][0] = t[i][1] = 0;
        for( int i = 1 ; i <= siz[u] ; ++ i )
            for( int j = 1 ; j <= siz[v] ; ++ j )
                ( t[i + j][0] += 1ll * dp[u][i][0] * dp[v][j][1] ) %= P,
                ( t[i + j][1] += 1ll * dp[u][i][1] * dp[v][j][1] ) %= P,
                ( t[i + j - 1][0] += 1ll * dp[u][i][0] * dp[v][j][0] ) %= P,
                ( t[i + j - 1][1] += ( 1ll * dp[u][i][0] * dp[v][j][1] % P + 1ll * dp[u][i][1] * dp[v][j][0] % P ) % P ) %= P;
        siz[u] += siz[v];
        for( int i = 1 ; i <= siz[u] ; ++ i ) dp[u][i][0] = t[i][0] , dp[u][i][1] = t[i][1];
    }
}
int Pow( int x , int a ) {
    int cur = x % P , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int J[MAXN] , invJ[MAXN] , re[MAXN];
int C( int a , int b ) {
    return 1ll * J[a] * invJ[b] % P * invJ[a - b] % P;
}
signed main() {
    cin >> n >> m;
    m = max( 0ll , n - 1 - m );
    J[0] = invJ[0] = 1;
    for( int i = 1 ; i < MAXN ; ++ i ) J[i] = 1ll * J[i - 1] * i % P , invJ[i] = Pow( J[i] , P - 2 );
    for( int i = 1 , u , v ; i < n ; ++ i ) {
        scanf("%lld%lld",&u,&v) , G[u].push_back( v ) , G[v].push_back( u );
    }
    dfs( 1 , 1 );
    int t = Pow( n , P - 2 );
    for( int i = 1 ; i <= n ; ++ i )
        re[i] = 1ll * dp[1][i][1] * t % P , t = 1ll * t * n % P;
    int res = 0;
    for( int i = m ; i < n ; ++ i ) {
        int r = 0;
        for( int j = i ; j < n ; ++ j )
            ( r += 1ll * C( j , i ) * re[n - j] % P * ( ( j - i & 1 ) ? P - 1 : 1 ) % P ) %= P;
        ( res += r ) %= P;
    }
    cout << res << endl;
}