どのように得たらいいか。部分集合か1つずつ確かめるのはさすがにTLE。減算とマスクを用いると、上手く全ての部分集合を得られる。全方位木DPと呼ばれるらしい。木DPは適当な1頂点を根とするが、全方位木DPは、全ての頂点を根として考えなければならない場合に使う(と思う)まずは普通に適当な頂点を根としてDFSなどで木DPする。その後、2回目のDFSを行う。根になった場合の答えを求めるのに必要な情報」を与えながら移動する。この値は根から累積的に計算できるようにしておく。遷移(1回目)探索方法は何でもよいが、頂点1から再帰的にDFSで求めるとする。子の1つを$u$とする。黒かったら$DP1[u]$通り。白かったら$u$以下の部分木は全て白く塗るしか無いので、1通り。以下の部分木に対して可能である。同様に$v$の各子供に対して求め、掛け合わせた数が、$DP1[v]$となる。根が指定されていればこれで良かった。遷移(2回目)同様にDFSで頂点1から探索するとする。伝えられているとする。2回目の遷移では、以下のことを行いたい。$p$から伝えられたので、情報が補完された。伸びるものだけを掛け合わせないパターン数」を伝えれば良い。割った値が入っている。いつものように素数とは限らないため、モジュラ逆数が使えない。要は割り算が出来ない。計算量が必要となり、特殊な入力でTLEする。このように、割り算が出来ない状況下で「ある集合から、1つだけを除いた積」を求めたい場合は、前後双方からの累積積を求めておくと良い。1前後の'1'は計算上の便宜的なものとする。6×77=462となる。(実際のindexは異なるが、イメージとして)各頂点についての子の累積積は、1回目の探索の際についでに求めたが、2回目の探索時にその頂点についてだけ構築した方がメモリに優しいね。部分木となった場合のパターン数を伝えられ、連鎖的に全頂点の答えが求められた。ikatakosメディアマネージャー文書の先頭へ。