Luogu
LOJ
UOJ
不管怎样先特判\(y=1\)的情况。
先考虑固定一棵树的情况。
设固定的树的边集为\(E_1\)，枚举的树的边集为\(E_2\)。
设\(f(T)=y^{n-|T|}\)，那么\(ans=\sum\limits_{E_2}f(E_1\cap E_2)\)。
考虑经典子集反演\(f(T)=\sum\limits_{S\subseteq T}\sum\limits_{R\subseteq S}(-1)^{|S|-|R|}f(R)\)。
因此我们有
\(ans=\sum\limits_{E_2}\sum\limits_{S\subseteq E_1\wedge S\subseteq E_2}\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|}\)
\(ans=\sum\limits_{S\subseteq E_1}(\sum\limits_{S\subseteq E_2}1)\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|}\)
设\(g(S)=\sum\limits_{S\subseteq E_2}1\)即包含\(S\)的树的个数
\(ans=\sum\limits_{S\subseteq E_1}g(S)\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}y^{n-|T|}\)
\(ans=\sum\limits_{S\subseteq E_1}g(S)y^{n-|S|}\sum\limits_{T\subseteq S}(-y)^{|S|-|T|}\)
\(ans=\sum\limits_{S\subseteq E_1}g(S)y^{n-|S|}(1-y)^{|S|}\)
推到这里差不多到底了，我们考虑一下\(g(S)\)。
假设\(S\)把\(n\)个点分成了\(m\)个连通块，每个连通块有\(a_i\)个点。
有点经验的话应该能够看出这是个Ex-Cayley定理的形式。
\(g(S)=n^{m-2}\prod\limits_{i=1}^ma_i\)
我们把这个代进去，注意\(n=|S|+m\)
\(ans=\sum\limits_{S\subseteq E_1}y^m(1-y)^{n-m}n^{m-2}\prod\limits_{i=1}^ma_i\)
\(ans=\frac{(1-y)^n}{n^2}\sum\limits_{S\subseteq E_1}(\frac{yn}{1-y})^m\prod\limits_{i=1}^ma_i\)
\(ans=\frac{(1-y)^n}{n^2}\sum\limits_{S\subseteq E_1}\prod\limits_{i=1}^m\frac{yn}{1-y}a_i\)
为了方便我们记\(k=\frac{yn}{1-y}\)。
这告诉我们每个大小为\(a_i\)连通块会产生\(ka_i\)的贡献，而一个边集的贡献为它划分的连通块的贡献之积，我们要求的是所有边集的贡献之和。
考虑dp计算这个贡献，一维看上去不太够就设两维，令\(f_{u,i}\)表示只考虑\(u\)的子树，\(u\)所在连通块的大小为\(i\)的所有边集方案在忽略\(i\)所在连通块之后的的贡献之和。
那么可以得到
\(ans=\frac{(1-y)^n}{n^2}\sum\limits_{i=1}^nkif_{1,i}\)
转移就是经典的树上背包。
考虑优化，令\(g_u=k\sum\limits_iif_{u,i},F_u(x)=\sum\limits_if_{u,i}x^i\)，那么我们有
\(F_u(x)=x\prod\limits_v(g_v+F_v(x))\)
\(g_u=kF_u'(1)\)
计算可得
\(g_u=k\prod\limits_v(g_v+F_v(1))+\prod\limits_v(g_v+F_v(1))\sum\limits_v\frac{kF_v'(1)}{g_v+F_v(1)}\)
这里的\(F_v'(1)=g_v\)，因此我们只关心\(F_u(1)\)，而显然有
\(F_u(1)=\prod\limits_v(g_v+F_v(1))\)
再令\(h_u=F_u(1)=\sum\limits_if_{u,i}\)，那么可以得到
\(h_u=\prod\limits_v(g_v+h_v)\)
\(g_u=h_u(k+\sum\limits_v\frac{kg_v}{g_v+h_v})\)
这样我们就可以直接\(O(n)\)计算出答案了。
顺带一提\(ans=\frac{(1-y)^n}{n^2}kg_1\)
原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12150695.html