似乎是第一次做這個樣子的容斥題。
給定一棵樹，把每條邊染成黑色或白色，有 \(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);
}