ABC152 F - Tree and Constraints - ツバサの備忘録

解法

あらかじめ、頂点 $i$ から $j$ へのパスに使われる辺の集合を表すビット列 $T_{ij}$ を、前計算で計算しておきます。これは、任意の頂点 $i$ からBFSで辿っていけば良いです。
$M$ 個の条件からいくつか選んだ、条件の集合 $S$ に対して以下のような数を計算します。

少なくとも $S$ に含まれる条件を全て満たさないような辺の色の決め方の場合の数

すると、包除原理によって、 $S$ に含まれる条件の個数が偶数なら求めた値を加算、奇数なら減算、を $2^{M}$ 通りの全ての $S$ について繰り返すと、求める答えとなります。

上で計算したかった値を $C_{S}$ とします。
$S$ に含まれる条件は全て満たさない、という仮定があるので、 $S$ に含まれる条件に指定されている辺は全て白くしなければなりません。
逆に、それ以外の辺については何も制約がないので、黒白どちらでも問題ありません。
条件に指定されていない辺の個数を $X$ とすると、
$C_{S} = 2^{X}$ となります。
あとは $S$ に対する $X$ が求まればよいです。
これは、 $S$ に含まれる全ての条件について使われる辺を洗いだし、それらの和集合を求めれば、その個数を $N-1$ から引けばよいです。これは、最初に前計算しておいたビット列を用いると、OR演算を用いて簡単に計算することができます。

感想

問題を見た時点で包除っぽい、となってから、 $M$ の制約に気づき、素直に考察が進んだと思います。