### [Link](https://www.luogu.com.cn/problem/P3349) 先考虑一个暴力点的想法：求出 $u$ 点编号为 $i$，且以 $u$ 为根的子树的编号集合为 $S$，的方案数。 发现瓶颈在于枚举子集，我们考虑容斥，只求出每个点的状态在 $S$ 中的方案数，最后容斥计算答案 $ans=f(S)\cdot (-1)^{n-|S|}$ 即可。 ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while(!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=20, M=(1<<17)+10; int n, m, g[N][N], f[N][N], popcnt[M], ans; vector<int> e[N], lst; void dfs(int u, int fa) { for (int v:e[u]) if (v!=fa) dfs(v, u); for (int i:lst) { f[u][i]=1; for (int v:e[u]) { if (v==fa) continue; int sum=0; for (int j:lst) { if (!g[i][j]) continue; sum+=f[v][j]; } f[u][i]*=sum; } } } void clear() { if (lst.empty()) return; for (int i=1; i<=n; i++) for (int j:lst) f[i][j]=0; lst.clear(); } signed main() { n=read(), m=read(); for (int i=1; i<=m; i++) { int u=read(), v=read(); g[u][v]=g[v][u]=1; } for (int i=1; i<n; i++) { int u=read(), v=read(); e[u].push_back(v); e[v].push_back(u); } int lim=1<<n; for (int i=0; i<lim; i++) popcnt[i]=popcnt[i>>1]+(i&1); for (int s=0; s<lim; s++) { clear(); for (int i=1; i<=n; i++) if (s&(1<<i-1)) lst.push_back(i); dfs(1, 0); int sum=0; for (int i:lst) sum+=f[1][i]; ans+=sum*(((n-popcnt[s])&1)?-1 : 1); } printf("%lld\n", ans); return 0; } ``` Loading... ### [Link](https://www.luogu.com.cn/problem/P3349) 先考虑一个暴力点的想法：求出 $u$ 点编号为 $i$，且以 $u$ 为根的子树的编号集合为 $S$，的方案数。 发现瓶颈在于枚举子集，我们考虑容斥，只求出每个点的状态在 $S$ 中的方案数，最后容斥计算答案 $ans=f(S)\cdot (-1)^{n-|S|}$ 即可。 ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while(!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=20, M=(1<<17)+10; int n, m, g[N][N], f[N][N], popcnt[M], ans; vector<int> e[N], lst; void dfs(int u, int fa) { for (int v:e[u]) if (v!=fa) dfs(v, u); for (int i:lst) { f[u][i]=1; for (int v:e[u]) { if (v==fa) continue; int sum=0; for (int j:lst) { if (!g[i][j]) continue; sum+=f[v][j]; } f[u][i]*=sum; } } } void clear() { if (lst.empty()) return; for (int i=1; i<=n; i++) for (int j:lst) f[i][j]=0; lst.clear(); } signed main() { n=read(), m=read(); for (int i=1; i<=m; i++) { int u=read(), v=read(); g[u][v]=g[v][u]=1; } for (int i=1; i<n; i++) { int u=read(), v=read(); e[u].push_back(v); e[v].push_back(u); } int lim=1<<n; for (int i=0; i<lim; i++) popcnt[i]=popcnt[i>>1]+(i&1); for (int s=0; s<lim; s++) { clear(); for (int i=1; i<=n; i++) if (s&(1<<i-1)) lst.push_back(i); dfs(1, 0); int sum=0; for (int i:lst) sum+=f[1][i]; ans+=sum*(((n-popcnt[s])&1)?-1 : 1); } printf("%lld\n", ans); return 0; } ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏