ABC149-F Surrounded Nodes
頂点ごとの寄与を確率に分解して考える．
ある頂点がカウントされる確率は「その頂点が白かつその頂点の子である部分木のうち2つ以上に黒が含まれている」確率である．
余事象を取る．「その頂点が黒，または（その頂点は白かつ部分木のうち黒が含まれているものは1つ以下）」の確率を求めれば良い．前者は$ 1/2なのですぐに求まる．後者の条件を考えると，部分木のサイズを$ c_1, \cdots, c_k として$ \frac{1}{2^N}+\sum \frac{1}{2^{N-c_k}}(1-\frac{1}{2^{c_k}}) となる．これを頂点$ 1,\cdots, Nと足し合わせると答えが求められる．
部分木のサイズを列挙するところが残されている問題になるが，通常の木DPで自分の子の方は求められ，根以外であれば親側のサイズは$ Nから自分以下の部分を引けば復元できる．全方位木DPをする必要はない．