即统计交集的连通块个数，并有 y c y^c yc 的贡献
对于问题 1 1 1：
考虑点 n − c n-c n−c 条边作为交集，即硬点出 c c c 个联通块，设每个联通块大小为 a i a_i ai，那么方案数就是 ∏ a i × n c − 2 \prod a_i\times n^{c-2} ∏ai×nc−2，求出 f c = ∏ a i × n n − c − 2 f_c=\prod a_i \times n^{n-c-2} fc=∏ai×nn−c−2 表示点 c c c 条边断掉的方案数， 然后二项式反演 （注意我们直接点联通块的话不好容斥） Ans = ∑ c y n ∑ j ≥ c y − c f j ( j c ) ( − 1 ) j − c = y n ∑ j ( − 1 ) j f j ∑ c ( j c ) y − c ( − 1 ) c = y n ∑ j f j ( y − 1 − 1 ) j \text{Ans}=\sum_c y^{n}\sum_{j\ge c}y^{-c}f_j\binom{j}{c}(-1)^{j-c}\\=y^n\sum_j(-1)^jf_j\sum_c\binom{j}{c}y^{-c}(-1)^c\\=y^n\sum_jf_j(y^{-1}-1)^j Ans=c∑ynj≥c∑y−cfj(cj)(−1)j−c=ynj∑(−1)jfjc∑(cj)y−c(−1)c=ynj∑fj(y−1−1)j 即断 t t t 条边的贡献是 ( y − 1 − 1 ) t × n − t × ∏ a i (y^{-1}-1)^t\times n^{-t}\times \prod a_i (y−1−1)t×n−t×∏ai，这些贡献都是树形 D P \mathcal{DP} DP 的时候可以顺便算上的，这样就避免了记录连通块个数
对于问题 2 2 2： 同上，考虑求出 f c = ( ∏ a i × n n − c − 2 ) 2 f_c=\Big(\prod a_i\times n^{n-c-2}\Big)^2 fc=(∏ai×nn−c−2)2 Ans = y n ∑ j f j ( y − 1 − 1 ) j = y n n − 4 ( y − 1 − 1 ) n ∑ j n 2 ( n − j ) ( y − 1 − 1 ) − ( n − j ) ( ∏ i = 1 n − j a i ) 2 = ⋯ × [ z n ] exp ( ∑ i ≥ 1 z i i 2 i i − 2 ( y − 1 − 1 ) − 1 n 2 i ! ) \text{Ans}=y^n\sum_jf_j(y^{-1}-1)^j\\=y^nn^{-4}(y^{-1}-1)^n\sum_j n^{2(n-j)}(y^{-1}-1)^{-(n-j)}\Big(\prod_{i=1}^{n-j} a_i\Big)^2\\=\dots\times[z^n]\exp\Big(\sum_{i\ge 1}\frac{z^ii^2i^{i-2}(y^{-1}-1)^{-1}n^{2}}{i!}\Big) Ans=ynj∑fj(y−1−1)j=ynn−4(y−1−1)nj∑n2(n−j)(y−1−1)−(n−j)(i=1∏n−jai)2=⋯×[zn]exp(i≥1∑i!zii2ii−2(y−1−1)−1n2)
