似乎是第一次做这个样子的容斥题。
给定一棵树,把每条边染成黑色或白色,有 \(m\) 个限制,限制了 \(u\to v\) 的路径上必须有至少一个黑色,求方案数。
“至少有一个”这是一个很难求的条件,所以可以反过来。
可题目和我以前做过的容斥题目都不一样,它反了后不是全部不满足的,而是至少有一个不满足的。
于是容斥公式就登场了!
\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{T\in S} (-1)^{|T|+1}\left|\bigcap_{i=1}^{|T|}S_{T_i}\right|
\]
这个柿子很早就知道,可今天是第一次用到呢!
让我们把现在的问题代入这个柿子里面。设 \(f(S)\) 表示 \(S\) 这个状态的约束要不满足的方案数。则所有不满足的并就是
\[\sum_{T\in S} (-1)^{|T|+1} f(T)
代码
#include <iostream>
#include <algorithm>
#define int long long
const int N = 55, M = 25;
int n, m, no[N][N], sta[M], ans, dep[N], fa[N];
int popcount(int x) { return x ? (popcount(x & (x-1)) + 1) : 0; }
void dfs(int u) {
dep[u] = dep[fa[u]] + 1;
for (int v = 1; v <= n; v++) {
if (v == fa[u] || no[u][v] == -1) continue;
fa[v] = u;
dfs(v);
}
}
void color(int &S, int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
while (dep[x] > dep[y]) S |= (1ll << no[x][fa[x]]), x = fa[x];
if (x == y) return;
while (fa[x] != fa[y]) {
S |= 1ll << no[x][fa[x]], S |= 1ll << no[y][fa[y]];
x = fa[x], y = fa[y];
}
S |= 1ll << no[x][fa[x]], S |= 1ll << no[y][fa[y]];
}
signed main() {
std::cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) no[i][j] = -1;
for (int i = 1, u, v; i < n; i++) {
std::cin >> u >> v;
no[u][v] = no[v][u] = i-1;
}
dfs(1);
std::cin >> m;
for (int i = 1, u, v; i <= m; i++) {
std::cin >> u >> v;
color(sta[i], u, v);
}
for (int i = 1; i < (1ll << m); i++) {
int S = 0;
for (int j = 0; j < m; j++)
if (i & (1ll << j)) S |= sta[j+1];
int an = 1ll << (n-1-popcount(S)), t = popcount(i);
if (t & 1) ans = ans + an; else ans -= an;
}
std::cout << ((1ll << (n-1)) - ans);
}