ABC152 F. Tree and Constraints

問題

N個の頂点からなる木が与えられる。この木の辺を白か黒で塗ることを考える。
M個の制約が与えられ、i番目の制約は「2つの頂点u_i, v_iのパス上の辺には黒色の辺が1つ以上存在しなければならない」となっている。

M個すべての制約を満たすような塗り方の通り数を答えよ。

制約

• 2 <= N <= 50
• 1 <= M <= min(20, N*(N-1)/2)

解法(辺に注目してbitDP)

各辺に注目すると、0個以上の制約に関連付いている。
辺を白に塗るか黒に塗るかで、すでに満たした条件かどうかの状態が変化していくので、これはbitDPで、
dp[i][j] := i番目までの辺で、すでに満たした場合bitが1になっているような条件の状態を表すjのときの通り数
として、dp[0][0] = 1からdp[i+1][j] += dp[i][j]かdp[i+1][j|mask] += dp[i][j](maskは辺iに関連する制約のbitマスク)で遷移させていけばよい。

解法(制約に注目して包除原理)

制約に注目すると、「制約をすべてを満たす」＝ U - 「制約を1つ以上満たさない集合」であり、「制約を1つ以上満たさない集合」は「各制約を満たさない集合」の和集合になっている。
したがって、この「各制約を満たさない集合の和集合」を求める。
これは、(制約1を満たさない集合) + (制約2を満たさない集合) - (制約1かつ制約2を満たさない集合)・・・のようになっており、包除原理で求められる。
また、制約を満たさない集合というのは、その制約すべてのパスの辺が白で塗られている場合なので、そのような塗り方は、白で塗る辺の数をxとして、「2^{N-1 - x}」で求められる。

うまく無駄な計算が発生しないようにしないとTLEするようなので、辺集合をbitで表現するなど無駄なループが発生しないよう気をつける。
(あと、解説放送で、途中計算がどこまで大きくなり得るか？が議論になってた)