关于二项式反演
假设现在需要从 \(n\) 个带标号球里面选 \(m\) 个，设 \(g(i)\) 表示钦定选了 \(i\) 个的方案数，设 \(f(i)\) 表示恰好选了 \(i\) 个的方案数。钦定的意思是让这 \(i\) 个必须选，其余随便，且"钦定"这个操作本身也有方案数。
则有 \(g(x)=\binom{n}{x}\times 2^{n-x}\)。这个式子的含义分成两步，即第一步选择 \(x\) 个物品，第二步在剩下物品中随意挑选。可以换个角度，先枚举总共选了 \(i\) 物品，再从这 \(i\) 个物品中选出第一步选出的 \(x\) 个物品，则有 \(g(x)=\sum \limits _{i=x}^n f(i)\binom{i}{x}\)。但是题目中一般会要求我们求出 \(f(x)\)，因为前面那个式子成立，则通过二项式反演的形式可以得到 \(f(x)=\sum \limits _{i=x}^n (-1)^{i-x} \binom{i}{x} g(i)\)。
故所谓的二项式反演，是你在得到一个式子后，用二项式反演反推的一种操作。一般 \(g(x)\) 比较好求，\(f(x)\) 不好求，就可以这样反推了。
关于 Prufer 序列和矩阵树定理求解图连通方案数
一个 \(n\) 个点 \(m\) 条边的带标号无向图有 \(k\) 个连通块。我们希望添加 \(k-1\) 条边使得整个图连通，求方案数。
设第 \(i\) 个联通块内的点的数量是 \(s_i\) 个。那么我们先把每一个联通块看成一个整体，枚举第 \(i\) 个联通块的度数为 \(d_i\)。则在 prufer 序列上出现次数为 \(d_i-1\)，且总共有 \(k-2\) 个数。则有：
其中，\({s_i}^{d_i}\) 的系数是因为这 \(k-1\) 条边，每一条边能带来 \(s_u\times s_v\) 的权值乘积，故一个点的度数若为 \(d_i\) 则有系数 \(s_i^{d_i}\)。
有多元二项式定理：
则上面那个式子可以写成 \((s_1+s_2+\dots+s_k)^{k-2}\times \prod s_i=n^{k-2}\times \prod \limits _{i=1}^k s_i\)。
关于本题
首先恰好 \(k\) 个公共边等价于分成 \(n-k\) 个联通块。定义 \(g(x)\) 表示钦定 \(x\) 个公共边的方案数，\(f(x)\) 表示恰好 \(x\) 个公共边的方案数。则有 \(f(x)=\sum \limits _{i=x}^n (-1)^{i-x} \binom{i}{x} g(i)\)。
考虑钦定怎么做，这需要我们选出恰好 \(x\) 个公共边，也就是分成恰好 \(n-x\) 个联通块，然后让这 \(n-x\) 个联通块之间连接。这符合钦定的定义。\(n-x\) 个联通块之间连接的方案数为 \(n^{n-x-2}\times \prod s_i\)。
也就是 \(g(x)\) 就等于选出 \(x\) 个公共边，形成的 \(\prod s_i\times n^{n-x-2}\) 的总和。将 \(n^{n-x-2}\) 提出去，就是求所有选择方案数的 \(\prod s_i\) 的总和。可以看成组合意义，每一个联通块里放一个小球的方案数。
定义 \(f_{i,j,0/1}\) 表示以 \(i\) 为根的子树，形成了 \(j\) 个联通块，包含 \(i\) 的联通块中有无小球的方案数。直接树上背包转移即可。复杂度 \(O(n^2)\)。