ABC149 F - Surrounded Nodes - ツバサの備忘録

解法

ある頂点が白であったときに、その頂点が $S$ に含まれる確率を計算します。すると、この確率は、どの頂点についても独立に計算できるので、全ての頂点について同じことを計算して足すことで、その総和が答えとなります。
また、確率は、 $S$ に含まれるパターン数を、 $2^{N}$ で割ったものになるので、 $S$ に含まれるパターン数を数えていきます。まず、今計算したい頂点が木全体の根であった場合について考えます。
根に対する子が $k$ 個存在していたとすると、その $k$ 個の頂点を根とする部分木について黒い頂点があるかどうかを調べたときに、2つ以上の部分木に黒い頂点が存在していれば、今計算したい頂点が $S$ に含まれることになります。
ある部分木 $i$ について、その部分木に含まれる頂点の個数を $c_{i}$ とします。すると、
全てが白になるパターンは明らかに1通りなので、少なくとも1つ以上の頂点が黒になるパターンは、 $(2^{c_i}-1)$ 通りになります。
ので、 $k$ 個の部分木について、2つ以上の部分木に、1つ以上の黒い頂点が含まれているようなパターンは、全体から、全て白の頂点になるパターンと、1つの部分木のみが黒い頂点を含み、それ以外の部分木は全て白の頂点になるパターンを引けばよいので、

$2^{N-1} - 1 - \sum(2^{c_{i}}-1)$

となります。
ある頂点 $x$ を根とした部分木の全体の頂点数は、適当にDFSをすることによって求めることができるので、上の計算をすることによって、木全体の根が白だった場合に、 $S$ に含まれるパターン数を計算することができました。
あとは、ある頂点が木全体の根でなかった場合に、その頂点が白かつ $S$ に含まれるパターン数です。
このときは、 $N - (今見ている頂点を根とする部分木の頂点数)$ を一つの部分木とします。これは、親を辿っていくことができる部分になります。この部分木と、もともとある子の部分木について、上と同様の計算をしてあげればよいです。

f:id:emtubasa:20191230163351p:plain

f:id:emtubasa:20191230163619p:plain

1つめの図が、根について見ているパターンです。枠で囲まれているのが、考慮すべき部分木です。
2つめの図が、根の子における頂点を1つピックアップしたパターンです。こちらも、枠で囲まれているのが、考慮すべき部分木です。
2つめの図において、茶色の部分木の頂点数を調べるには、青、水、緑の部分木の頂点数の総和+今見ている頂点自身を、 $N$ から引いてあげればよいです。
青、水、緑の部分木の頂点数は、1つめの図で頂点数を数える時点で計算済みのはずなので、これで簡単に計算することができます。もしくは、 $N$ から、赤い枠の頂点数をひけばよいです。
全ての頂点数について、 $2^{N-1} - 1 - \sum(2^{c_{i}}-1)$ を計算したら、これを $2^{N}$ で割ったものが答えになります。