ABC152 F - Tree and Constraints (600)
一つ以上黒は考えづらい条件なので全て白になる場合がある場合について考える
先にM個の条件について経路上の辺をDFSで求めておく
包除原理を用いて、
偶数個条件を満たさない場合は加算
奇数個条件を満たさない場合は減算
その場合の数は条件を満たさない経路上に含まれていない辺の個数を白黒それぞれに塗り分けた場合の数
事前の経路を求めるのが$ O(MN)、包除原理のそれぞれの場合を求めるところが$ O(2^MMN)
このままだと包除原理の部分が重いが、経路上の辺をビットで管理することで$ O(2^MM)になる
全体で$ O(MN + 2^MM)