包除原理をとても素朴な状態で問いかける問題!!!
問題概要
頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。
- 個目の制約は 2 頂点 が指定され、 と とを結ぶパスには黒辺が含まれるようにする
制約
考えたこと
まず一目思うこととして
- パス a-b 中のうち一つ以上を黒辺にせよ
という制約はとても扱いづらい!!!!!しかも「扱いづらい制約が 個あってすべて満たす必要がある」という状況。こういうのは包除原理でうまくいくことがよくある。こんな風にする:
(制約をすべて満たすもの) = (全部の塗り方) - (制約のうち 1 個以上を満たさないもの) + (制約のうち 2 個以上を満たさないもの) - (制約のうち 3 個以上を満たさないもの) + ...
たとえば のときは、こうなる。
(制約 1, 2, 3 をすべて満たすもの) = (全部の塗り方) - 制約 1 を満たさないもの - 制約 2 を満たさないもの - 制約 3 を満たさないもの + 制約 1, 2 を満たさないもの + 制約 2, 3 を満たさないもの + 制約 3, 1 を満たさないもの - 制約 1, 2, 3 を満たさないもの
満たさない制約番号の指定の仕方は 通りある。それぞれについて、以下のようにすればよい。
- 満たさない制約番号の集合を としたとき ( 個)
- これらの制約を満たさない場合の数を として
- とする
よって、それぞれの についての の計算に要する時間を としたならば、計算量は となる。次に の計算の仕方を考える。
DFS
番目の制約を満たさないものを数え上げることを考える。これはつまり、
- 本のパスが与えられるので
- それらのパス上の辺はすべて白色となるようにする
ということになる。よって、 本のパスに含まれるような辺の本数を としたならば、それらは白色に塗った上で、残りの 本については自由に着色してよいので 通りとなる。よって問題は「パス中の辺を列挙する」という問題になった。
これは DFS でできる。ただしいつもの DFS と違って、パスの復元をする必要があるので少し工夫が必要になる。
前処理
実装上は 個のパスそれぞれに対して、パスに含まれる辺集合を列挙しておくとよさそう。さらに、辺の本数はたかだか 50 本なので、辺集合は long long 型の変数として管理できる。
全体の計算量は、包除原理の各ステップについて、 だが、long long 型変数の OR 演算で表せることから実質 という感じになる。なのでちゃんとした計算量は だが、実質 という感じになる。
#include <iostream> #include <vector> using namespace std; using Edge = pair<int, int>; using Graph = vector<vector<Edge>>; int N, M; Graph G; vector<int> us, vs; bool rec(int v, int p, int target, long long &path) { if (v == target) { path = 0; return true; } for (auto e : G[v]) { if (e.first == p) continue; if (rec(e.first, v, target, path)) { path |= (1LL<<e.second); return true; } } return false; } long long solve() { vector<long long> paths(M, 0); for (int i = 0; i < M; ++i) rec(us[i], -1, vs[i], paths[i]); long long res = 0; for (long long bit = 0; bit < (1<<M); ++bit) { long long val = 0; for (int i = 0; i < M; ++i) if (bit & (1LL<<i)) val |= paths[i]; long long remnum = N-1 - __builtin_popcountl(val); if (__builtin_popcountl(bit) % 2 == 0) res += 1LL<<remnum; else res -= 1LL<<remnum; } return res; } int main() { cin >> N; G.assign(N, vector<Edge>()); for (int i = 0; i < N-1; ++i) { int x, y; cin >> x >> y; --x, --y; G[x].emplace_back(y, i); G[y].emplace_back(x, i); } cin >> M; us.resize(M), vs.resize(M); for (int i = 0; i < M; ++i) { cin >> us[i] >> vs[i]; --us[i], --vs[i]; } cout << solve() << endl; }