算法
(染色问题、容斥原理) $O(2^M \cdot M)$
显然只考虑 $u \to v$ 的路径上所有边都染白色会比较方便
奇数个集合相交取 -
号,偶数个集合相交取 +
号
根据归纳法可以得到 $f({\bigcap\limits_{i = 1}^n {{A_i}} }) = \sum\limits_{J \subseteq \left\{ {1,…,n} \right\}} {{{\left( { - 1} \right)}^{\left| J \right|}}f\Big( {\bigcap\limits_{j \in J} {\overline {{A_j}} } } \Big)}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
struct Edge {
int to, id;
Edge(int to, int id): to(to), id(id) {}
};
vector<Edge> g[55];
// 找到 v 到 tv 路径上的所有 id
vector<int> es;
bool dfs(int v, int tv, int p = -1) {
if (v == tv) return true;
for (Edge e : g[v]) {
if (e.to == p) continue;
if (dfs(e.to, tv, v)) {
es.push_back(e.id);
return true;
}
}
return false;
}
int main() {
int n;
cin >> n;
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
int m;
cin >> m;
vector<ll> eset(m);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
es = vector<int>();
dfs(a, b);
for (int e : es) {
eset[i] |= 1ll<<e;
}
}
ll ans = 0;
rep(i, 1<<m) {
ll mask = 0;
rep(j, m) {
if (i>>j&1) mask |= eset[j];
}
int white = __builtin_popcountll(mask);
ll now = 1ll<<(n - 1 - white); // 2^(n - 1 - white)
if (__builtin_popcountll(i) % 2 == 0) ans += now;
else ans -= now;
}
cout << ans << '\n';
return 0;
}
“难起来了”