题解 | D. Rebuild Tree

D. Rebuild Tree

前置芝士：prufer序列

prufer序列是将n个点的标号的无根树对应到长度为n-2，每个位置值域为[1,n]的序列。

prufer序列的构造方法是每次将树中编号最小的树叶删除，将树叶连接的点加入prufer序列。

树上点x的度数=prufer序列中x出现的次数+1。

Solution

题意相当于砍掉k条边再加上k条边，构成一棵树的方案数。

首先来考虑当砍掉的k条边确定时，此时树被分成了k+1棵树，我们设每棵树的节点个数是 $s_i$

我们把这些树抽象成点，因为最终就是要在这k+1棵树之间连k条边使得最终成一棵树；考虑当连边的方案已经确定时

此时这k+1个点构成的树的prufer序列也已经确定，还原到真实的方案树还要乘上每条边连到了哪个点的方案数，显然对于同一棵树内，连哪个点都是可以的，所以我们需要乘上 $\prod\limits_{i=1}^{k+1}s_i^{d_i}$ ，其中 $d_i$ 表示i的度数，由prufer序列的知识我们可以得知，这个式子可以写成 $\prod\limits_{i=1}^{k+1}s_i^{P_i+1}=\prod\limits_{i=1}^{k+1}s_i^{P_i}\times\prod\limits_{i=1}^{k+1}s_i$

发现 $\prod\limits_{i=1}^{k+1}s_i$ 与连边的方案无关，那么这部分就可以提出来，此时这k+1棵树的总贡献就可以写成 $\prod\limits_{i=1}^{k+1}s_i\times(\sum\limits_{\rm Tree(k+1)}\prod\limits_{i=1}^{k+1}s_i^{P_i})$

考察右边的式子， $P_i$ 是i树在prufer序列中出现的次数，我们知道，此时的prufer序列长度是 $k+1-2=k-1$ ，每个位置的值域在[1,k+1]，而当一个位置选 $i$ 的时候，算回总贡献是要乘上 $s_i$ 的，也就是说一种选择方案的贡献不是1，而是 $\prod\limits_{i=1}^{k-1}s_{P_i}$ ，那么 $(k+1)^{k-1}$ 种prufer序列的总贡献其实就是 $(\sum\limits_{i=1}^{k+1}s_i)^{k-1}=n^{k-1}$

那么我们的答案就简化为 $n^{k-1}\prod\limits_{i=1}^{k+1}s_i$

所以只需要算出 $\sum\limits_{\rm split(n,k)}\prod\limits_{i=1}^{k+1}s_i$

考虑将问题转化为等价问题：删掉 $k$ 条边且在每个联通块选一个点的方案数。

设 $dp[i][j][0/1]$ 表示 $i$ 子树内，删掉了 $j$ 条边， $i$ 所在的联通块是否选了点的方案数

然后就是经典树上背包了

ll dp[N][101][2], tmp[101][2];
int n, k, sz[N];
vector<int>to[N];
ll ksm(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, (a *= a) %= mod)
        if (b & 1)(ans *= a) %= mod;
    return ans;
}
void DP(int x, int fa) {
    sz[x] = 1;
    dp[x][0][0] = 1;
    dp[x][0][1] = 1;
    for (auto y : to[x]) {
        if (y == fa)continue;
        DP(y, x);
        memset(tmp, 0, sizeof(tmp));
        for (int i = 0; i < sz[x] && i <= k; ++i) {
            for (int j = 0; j < sz[y] && i + j <= k; ++j) {
                //不删当前边
                (tmp[i + j][0] += dp[x][i][0] * dp[y][j][0] % mod) %= mod;
                (tmp[i + j][1] += dp[x][i][1] * dp[y][j][0] % mod + dp[x][i][0] * dp[y][j][1] % mod) %= mod;
                if (i + j == k)continue;
                //删除当前边
                (tmp[i + j + 1][0] += dp[x][i][0] * dp[y][j][1] % mod) %= mod;
                (tmp[i + j + 1][1] += dp[x][i][1] * dp[y][j][1] % mod) %= mod;
            }
        }
        memcpy(dp[x], tmp, sizeof(tmp));
        sz[x] += sz[y];
    }
}

int main() {
    n = fast_IO::read(), k = fast_IO::read();
    for (int i = 1; i < n; ++i) {
        int x = fast_IO::read(), y = fast_IO::read();
        to[x].push_back(y);
        to[y].push_back(x);
    }
    DP(1, 0);
    printf("%lld", dp[1][k][1] * ksm(n, k - 1) % mod);
    return 0;
}