CF917D Stranger Trees

Description

给定一棵有 $n$ 个节点的树。求对于每个 $k\in[0,n-1]$，有多少棵由这 $n$ 个点之间的边构造成的树，与给定的树恰好有 $k$ 条边重复。答案对 $10^9+7$ 取模。
$n\leq 100$

Solution

题设中要求「恰好」$k$ 条边，我们考虑转化为「至少」 $k$ 条边。
那么相当于我们钦定连接 $k$ 条边，剩下的边全部断掉变成 $n-k$ 个连通块，再任意连 $k$ 条边将这些连通块连起来。求这玩意的方案数。
有一个小结论：$k$ 个大小为 $a_i$ 的连通块连接成 $n(n=\sum a)$ 个点的树的方案数为

$n^{k-2}\prod_{i=1}^{k}a_i$

证明过程可以先考虑最基本的式子

$\sum_{T}\prod_{(u,v)\in T}a_u\times a_v$

设 $d_i$ 表示第 $i$ 个连通块最后的度数，可以得到

$\sum_{T}\prod a_i^{d_i}$

此时可以从 $\text{Prufer}$ 序列入手考虑。因为一个度数为 $d_i$ 的点在 $\text{Prufer}$ 序列中只会出现 $d_i-1$ 次。

$\sum_{\sum d_i=2k-2}(\binom{2k-2}{d_1-1,\cdots,d_k-1}\prod_{i=1}^{k}a_i^{d_i})$

令 $e_i = d_i - 1$ ，得

$\prod_{a_i}\sum_{\sum e_i=k-2}(\binom{k-2}{e_1,\cdots,e_k}\prod_{i=1}^{k}a_i^{e_i})$

由多项式定理可得

$n^{k-2}\prod_{i=1}^{k}a_i$

回到问题。可以发现，断边后连边的方案数只与断边后的连通块数和断边后每个连通块的大小之积的和有关。而前者是定值，我们只需要考虑后者。

「连通块大小之积」可以转化为断完边后，从每个连通块内选一个点的方案数。假设断 $k$ 条边，那么我们可以先提前钦定 $k+1$ 个点，再转化为断边使之两两不连通的方案数。树上选点的 DP 是比较好处理的。设 f[p][i][0/1] 表示在 $p$ 子树内选 $i$ 个钦定的点，$p$ 连通块内是否有钦定的点的方案数。注意到我们必须保证子结点连通块必须有且仅有一个钦定节点，所以考虑当前边断与不断，可以写出如下转移方程：

$f_{p,i+j,1}\leftarrow f_{p,i,1}\times f_{u,j,0} + f_{p,i,1}\times f_{u,j,1} + f_{p,i,0}\times f_{u,j,1}\\ f_{p,i+j,0}\leftarrow f_{p,i,0}\times f_{u,j,0} + f_{p,i,0}\times f_{u,j,1}$

卡卡上下界可以做到 $\mathcal{O}(n^2)$ 转移。最后断 $i$ 条边的答案就是 $f[\text{rt}][n-i][1]$ 。

有些小朋友可能会对 $f_{p,i+j,0}\leftarrow f_{p,i,0}\times f_{u,j,1}$ 有疑问，因为这条转移相当于断边，但是万一这条边不该断呢？事实上没有关系，我们只需要保证断边时子节点有钦定的节点即可，最后要用的就是 $f[\text{rt}][n-i][1]$，这里是不会有错误转移的。

假设「至少」重复 $k$ 条边的答案为 $g_k$ ，「恰好」重复 $k$ 条边的答案为 $f_k$ ，则

$\begin{aligned} g_k&=n^{n-k-2}f[\text{root}][n-k][1] \\ &=\sum_{i=k}^{n-1}(-1)^{i-k}\binom{i}{k}f_i \end{aligned}$

二项式反演就可以得到 $f_i$ 的式子了。

总复杂度 $\mathcal{O}(n^2)$ 。

官方给的做法也挺有意思。考虑原图的完全图，给树边定为 $x$ ，非树边定为 $1$ ，那么矩阵树后 $x^k$ 的系数就是恰好重复 $k$ 条边的方案数。
不方便带着多项式做矩阵树定理？可以带入 $n$ 个点值进去算，然后插值插出来。复杂度 $\mathcal{O}(n^4)$

Code

代码给的是第一种方法

const int N = 1e2 + 5, mod = 1e9 + 7;
using namespace std;
int n, num;
int g[N], sz[N], c[N][N], head[N], nt[N << 1], to[N << 1];
void Add(int x, int y){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y;
    ++num, nt[num] = head[y], head[y] = num, to[num] = x;
}
int Q(long long b, int t){
    long long ret = 1; if(t == -1) t = mod - 2;
    for(unsigned i = 1; i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
long long f[N][N][2], tmp[N][2];
void dfs(int p, int fa){
    f[p][0][0] = f[p][1][1] = 1; sz[p] = 1;
    for(int i = head[p]; i; i = nt[i]){
        int v = to[i]; if(v == fa) continue;
        dfs(v, p); 
        memset(tmp, 0, sizeof tmp);
        for(int i = 0; i <= sz[v]; ++i)
        for(int j = 0; j <= sz[p]; ++j){
            tmp[i + j][0] += (f[v][i][0] * f[p][j][0] % mod + f[v][i][1] * f[p][j][0] % mod) % mod;
            tmp[i + j][1] += (f[v][i][0] * f[p][j][1] % mod + f[v][i][1] * f[p][j][1] % mod + f[v][i][1] * f[p][j][0]) % mod;
        } 
        sz[p] += sz[v];
        for(int i = 0; i <= sz[p]; ++i)
            f[p][i][0] = tmp[i][0] % mod, f[p][i][1] = tmp[i][1] % mod;
    } 
}
int main(){

    r(n);
    for(int i = 1, x, y; i < n; ++i)
        r(x, y), Add(x, y);
    dfs(1, 0);
    for(int i = 0; i < n; ++i)
        g[i] = 1ll * Q(n, n - i - 2) * f[1][n - i][1] % mod;
    c[0][0] = 1;
    for(int i = 1; i < n; c[i][0] = 1, ++i)
    for(int j = 1; j < n; ++j)
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    for(int i = 0; i < n; ++i){
        long long ans = 0;
        for(int j = i; j < n; ++j)
            if(j - i & 1) ans += mod - 1ll * c[j][i] * g[j] % mod;
            else ans += 1ll * c[j][i] * g[j] % mod;
        w(ans % mod, ' ');
    }
    return 0;
}