問題リンク
問題概要
\(N\)頂点の木が与えられる。\(N-1\)本の辺を白または黒に塗り分ける方法であって、次の\(M\)個の条件全てを満たすものはいくつあるか。
- 条件\(i(1≦i≦M) \) : \(u_i\)と\(v_i\)を結ぶパスの間に、黒い辺が少なくとも1つ存在する
解法
条件\(1…M\)を1つでも満たさない物の個数を数え、最後に\(2^{N-1}\)から引いて答えを求める。
各辺に適当に番号を振っておく。 点\(u_i\)と\(v_i\)を結ぶパスに含まれる辺の集合を\(P_i\)とすると、条件iを満たさないことと\(P_i\)に含まれる辺が全て白く塗られていることは同値である。よって条件iを満たさない塗り方の総数は\(2^{N-1-P_i}\)である。
複数個の条件に対しても和集合に対して要素数を数えて同様に計算できる。
包除原理を使って求めたいものが得られる。
なお、辺の集合は (辺eが含まれる⇔下からe番目のbitが立っている) とする整数で管理した。
提出
https://atcoder.jp/contests/abc152/submissions/9616664
感想
包除原理がスムーズに書けて良かった。
