AtCoder Beginner Contest 149 F - Surrounded Nodes

F - Surrounded Nodes 問題 $n$ 頂点の木が与えられる. 今からこの木の各頂点を,独立に確率 $\frac{1}{2}$ で黒か白に塗る. 塗り終わった後,黒い頂点を全て含む最小の部分木 $S$ を取