https://atcoder.jp/contests/abc152/tasks/abc152_f
$N$頂点の木と$M$個の頂点のペアが与えられる。この木にある$N-1$本の辺を白と黒に塗り分けることを考える。ここで、頂点の各ペアは以下のような制約を表す
$M$個の制約すべてを満たすような辺の塗り分けかたの個数を求めよ。
「pathを構成する辺のうち少なくとも1辺が黒でなくてはならない」は「pathを構成する辺がすべて白であってはならない」と言い換えることができる。このとき、「$2^{N-1}-$すべて白であるようなpathが一つでもあるような塗り方」を求めれば良いから、これを包除原理で求めることができる。
具体的には、各辺についてどのpathに関係しているかを記録したあと、すべて白に塗るpathの組み合わせを全探索する。このとき、$2^{N-1-C}$通りの塗り方がある。ここで$C$は選んだpathの集合のうち1つ以上に含まれている辺の数である。あとは選んだ集合に含まれるpathの数が偶数のときこれを答えに足し、奇数のとき引けば良い。
包除原理の問題、実はABCレベルだとあまり見ないかもしれない。木上でDFSしながらある二点間のpathに含まれる辺を列挙する方法について、解説放送を見たらいい方法を知ることができた。