【题解】CF917D Stranger Trees

· · 题解

题意

给定 n 个节点的树，考虑下列问题：

求有多少棵不同的树满足：与给定树重合的边恰好有 x 条。
两棵树不同当且仅当存在边 (u,v) 在一棵树中出现且不在另一棵树中出现。

对 x=0,1,\cdots,n-1 分别求出上述问题的答案。

数据范围：n \le 100。（可做到 O(n^2) 或更低的时间复杂度）

题解

记上述问题的答案为 f_x，发现 f 很难求，考虑转化。

考虑容斥：设 g_x 表示包含给定树中 x 条边的树的数量（不要求其它 n-1-x 条边不被包含；对于不同的 x 条边，同一棵树可能被计算多次），则有：

f_x=\sum_{i=x}^{n-1}(-1)^{i-x}\binom{i}{x}g_i

（即运用了二项式反演，证明可参考xyyxyyx 的博客 - 二项式反演证明，亦可仿照这篇题解中子集反演证明的部分，列出初始恒等式进行证明）

因此可以在 O(n^2) 的时间里用 g 求得 f，接下来考虑如何求 g。

有一个重要的结论：

若 n 个点的无向图中有 k 个连通块，且其中第 i 个连通块大小为 s_i，则把这 k 个连通块用 k-1 条边连通起来的方案数为 \prod{s_i} \cdot n^{k-2}。

可以使用无根树的 Prufer 序列证明，也可以使用矩阵树定理证明。

具体可参考OI Wiki - 图连通方案数（Prufer 序列+多项式定理）和Soulist 的题解（矩阵树定理 & Prufer 序列+EGF）

包含给定树中 x 条边等价于有 n-x 个连通块，因此我们只需对每个 x 计算出所有情况的 \prod{s_i} 之和，并乘上 n^{n-x-2} 即可。

考虑树形背包 DP，设 f_{u,i,j} 表示：考虑以 u 为根的子树，将其分成 i 个连通块，且 u 所在连通块大小为 j 的所有情况的 \prod{s_i} 之和（还未乘上 j）。不难想到转移：

f_{u,x,a} \cdot f_{v,y,b} \cdot b \to f'_{u,x+y,a} f_{u,x,a} \cdot f_{v,y,b} \to f'_{u,x+y-1,a+b}

其中 f' 表示更新后的 f，v 是 u 的儿子。（后文表示相同含义）

说明：第一行表示不合并，第二行表示将 v 所在连通块与 u 所在连通块合并。

树上背包是 O(n^2) 的（因为任意两个点只会在它们的 LCA 处合并恰好一次），算上额外的一维是 O(n^3) 的，可以继续优化。

有一个经典的 Trick：各部分数量之积等于在每一部分选一个元素的方案数。

因此把第三维改为是否已选过：设 f_{u,i,k} 表示，考虑以 u 为根的子树，将其分成 i 个连通块，且未/已选择好 u 所在连通块的点（k=0/1）。类似地可得转移：

f_{u,x,0} \cdot f_{v,y,1} \to f'_{u,x+y,0} f_{u,x,1} \cdot f_{v,y,1} \to f'_{u,x+y,1} f_{u,x,0} \cdot f_{v,y,0} \to f'_{u,x+y-1,0} f_{u,x,1} \cdot f_{v,y,0}+f_{u,x,0} \cdot f_{v,y,1} \to f'_{u,x+y-1,1}

说明：

初始时 f_{u,1,0}=f_{u,1,1}=1。

总时空复杂度为 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=100+5;
int End[max_n<<1],Last[max_n],Next[max_n<<1],e;
inline void add_edge(int x,int y)
{
    End[++e]=y,Next[e]=Last[x],Last[x]=e;
    End[++e]=x,Next[e]=Last[y],Last[y]=e;
}
const int mod=1e9+7;
inline int get_sum(int a,int b)
{
    return a+b-(a+b>=mod?mod:0);
}
int sz[max_n],dp[max_n][max_n][2],f[max_n][2];
void dfs(int x,int fa)
{
    dp[x][1][0]=dp[x][1][1]=1,sz[x]=1;
    for(int i=Last[x];i;i=Next[i])
    {
        int y=End[i];
        if(y!=fa)
        {
            dfs(y,x);
            for(int j=1;j<=sz[x];++j)
                for(int k=1;k<=sz[y];++k)
                {
                    f[j+k][0]=(f[j+k][0]+1ll*dp[x][j][0]*dp[y][k][1])%mod;
                    f[j+k][1]=(f[j+k][1]+1ll*dp[x][j][1]*dp[y][k][1])%mod;
                    f[j+k-1][0]=(f[j+k-1][0]+1ll*dp[x][j][0]*dp[y][k][0])%mod;
                    f[j+k-1][1]=(f[j+k-1][1]+1ll*dp[x][j][1]*dp[y][k][0]+1ll*dp[x][j][0]*dp[y][k][1])%mod;
                }
            sz[x]+=sz[y];
            for(int j=1;j<=sz[x];++j)
                for(int k=0;k<=1;++k)
                {
                    dp[x][j][k]=f[j][k];
                    f[j][k]=0;
                }
        }
    }
}
int C[max_n][max_n],Pow[max_n];
inline void init(int n)
{
    for(int i=0;i<=n;++i)
    {
        C[i][0]=1;
        for(int j=1;j<=i;++j)
            C[i][j]=get_sum(C[i-1][j-1],C[i-1][j]);
    }
    Pow[0]=1;
    for(int i=1;i<=n;++i)
        Pow[i]=1ll*Pow[i-1]*n%mod;
}
int F[max_n],G[max_n];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n-1;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
    }
    dfs(1,0);
    init(n);
    for(int i=0;i<=n-2;++i)
        G[i]=1ll*dp[1][n-i][1]*Pow[n-i-2]%mod;
    G[n-1]=1;
    for(int i=0;i<=n-1;++i)
    {
        for(int j=i;j<=n-1;++j)
        {
            if((j^i)&1) // (j-i)&1
                F[i]=(F[i]-1ll*C[j][i]*G[j])%mod;
            else
                F[i]=(F[i]+1ll*C[j][i]*G[j])%mod;
        }
        F[i]+=F[i]<0?mod:0;
        printf("%d%c",F[i],i<n-1?' ':'\n');
    }
    return 0;
}

彩蛋

这里是本题解的写作背景。（果然有题目背景就会有题解背景吗（雾））

本文的目的之一：祭奠纪念自己在模拟赛中做不出来原题。

同时谴责出题人/组题人在模拟赛中放（我不会大家都会的）原题！！！

本篇文章的完成时间为 2021.11.2，结合创建时间可知，这是当时留的一个坑。

大约四个月前的我在阅读了 Soulist 的题解以后大有收获，打算写一篇题解。

可后来由于各种各样的原因咕掉了……

今天模拟赛恰好考到了这道题（唯一的区别：n 开大到了 8000，且略微卡空间），而我完全没有意识到这是自己做过的原题 /wul。

尽管我想到了用二项式反演做恰好和至少的转化，想到了用 Prufer 序列和 Matrix Tree 定理推一推式子，且隐隐约约觉得会有什么结论。

我最终没能推出来式子，并且还发现自己对 Matrix Tree 定理的记忆十分模糊，以至于根本无法应用……

最终只好打了个 O(n^{n-1}) 的暴力走人……

经同学一提醒，翻出原题瞬间想起了一切……

于是我今天一口气把这个坑填了！