LOJ#3399. 「2020-2021 集训队作业」Communication Network

组合意义妙妙题，也可以用容斥暴力处理。

太厉害了！！！

暴力容斥

设 $\displaystyle f(S)=|S|\cdot 2^{|S|}$，答案为 $\displaystyle \sum_{T_2}f(T_1\cap T_2)$。并集的限制似乎必须要枚举，我们考虑子集容斥得到：

$$\begin{align} \sum_{T_2}\sum_{S\subseteq (T_1\cap T_2)}\sum_{T\subseteq S}(-1)^{|S|-|T|} |T|\cdot 2^{|T|}\notag\\ \end{align}$$

这里使用组合意义，我们直接枚举并集，贡献就是包含边集 $S$ 的生成树个数，设为 $g(S)$。进一步得到下面的式子，并进行推导：

$$\begin{align} &\sum_{S\subseteq T_1}g(S)\sum_{T\subseteq S}(-1)^{|S|-|T|} |T|\cdot 2^{|T|}\notag\\ =&\sum_{S\subseteq T_1}(-1)^{|S|}g(S)\sum_{T\subseteq S}(-1)^{|T|} |T|\cdot 2^{|T|}\notag\\ =&\sum_{S\subseteq T_1}(-1)^{|S|}g(S)\sum_{i=0}^{|S|}\binom{|S|}{i}(-2)^{i}\cdot i\notag\\ =&\sum_{S\subseteq T_1}(-1)^{|S|}g(S)\cdot |S|\sum_{i=1}^{|S|}\binom{|S|-1}{i-1}(-2)^{i}\notag\\ =&\sum_{S\subseteq T_1}(-1)^{|S|}g(S)\cdot (-2|S|)\sum_{i=0}^{|S|}\binom{|S|-1}{i}(-2)^{i}\notag\\ =&\sum_{S\subseteq T_1}(-1)^{|S|}g(S)\cdot (-2|S|)\cdot (-1)^{|S|-1}\notag\\ =&2\sum_{S\subseteq T_1}|S|\cdot g(S)\notag\\ \end{align}$$

根据 Prufer 序列经典结论：$\displaystyle g(S)=n^{k-2}\prod_{i=1}^{k} a_i$，其中 $k$ 为连通块个数，$a_i$ 为连通块大小。这有比较显然的组合意义，$k-2$ 等于删去的边减一，可以看成每条删去的边使答案乘 $n$，最后再将答案除以 $n$。那么 $\prod_{i=1}^{k} a_i$ 在每个连通块中选一个点的方案数。我们直接 DP 就好了。

组合意义

我们直接对 $n\cdot 2^n$ 使用组合意义，$n$ 相当于选一条边，$2^n$ 相当于选择一条公共边乘 $2$，但是这涉及到找出所有公共边的问题（直接处理的方式就是上面的容斥）。重新考虑其组合意桜流し义，可以看成 $2^n=(1+1)^n$，相当于选取一个公共边的子集。两部分合起来相当于钦定一条公共边，再钦定一些公共边。 我们会得到与上面一样的式子。