ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

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の制約に気づき、素直に考察が進んだと思います。