T2

考虑提取出某个树上连通块的代表元

发现对于每个连通块，它的根都是唯一的

所以 树上连通块的数量 = 树上无父亲点的数量

期望其实就是 $\frac{\sum_{p \in S} X_pY_p}{\mid S\mid}$ ,其中 $\mid S \mid = 2^{n}$

变成求 $\sum\limits_{p\in S}X_pY_p$

考虑对 $X_p$ 分解，变为每个点无父亲时的贡献

也就是 $\sum\limits_{i=1}^{n}E(i,fa_i)$ ，$E(i,j)$ 表示点 $i$ 必选 点 $j$ 必不选时第二棵树的贡献和

我们发现这其实等价于 点 $i$ 必选的贡献 - 点 $i,j$ 必选的贡献

考虑怎么求点 $i,j$ 必选的贡献，考虑从一开始的 $dp$ 开始入手

一开始，我们设 $f_{i,0/1}$ 表示在以点 $i$ 为根的子树中，点 $i$ 选/不选的期望

那么有
$$
f_{u,1}=\sum_{v\in son_u} \frac12(f_{v,0}+f_{v,1})\

f_{u,0}=\frac{\mid son_u \mid}{2}+\sum_{v\in son_u} \frac12(f_{v,0}+f_{v,1})\

$$
当某个点必选时，相当于某个点处的 $f_{u,0}$ 强制设为了 $0$ ，把二分之一去掉，楼上的加上 $\frac12$ 然后更新 $dp$ ，得到的 $f_{0,0}$

当某个点必选时，相当于某个点处的 $f_{u,1}$ 强制设为了 $0$ ，把二分之一去掉，楼上的减去 $\frac12$ 然后更新 $dp$ ，得到的 $f_{0,0}$

不妨设 $g_u=f_{u,0}+f_{u,1}$ ，那么有
$$
g_{u}=\frac{\mid son_u \mid}{2}+\sum_{v\in son_u} g_v\

\begin{eqnarray}f_{0,0} &=& g_0-f_{0,1}\
&=& g_0-\frac12\sum_{v\in son_0} g_v\
&=& g_0-\frac12g_1\
\end{eqnarray}
$$
考虑转变为求 $g_u$