洛谷P3349 [ZJOI2016]小星星 题解
题目链接：P3349 [ZJOI2016]小星星
题意：
cxy 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 $n$ 颗小星星，用 $m$ 条彩色的细线串了起来，每条细线连着两颗小星星。
有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 $n-1$ 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。cxy 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。cxy 想知道有多少种可能的对应方式。
只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。
输入格式：
第一行包含 $2$ 个正整数 $n,m$，表示原来的饰品中小星星的个数和细线的条数。
接下来 $m$ 行，每行包含 $2$ 个正整数 $u,v$，表示原来的饰品中小星星 $u$ 和 $v$ 通过细线连了起来。这里的小星星从 $1$ 开始标号。保证 $u\neq v$，且每对小星星之间最多只有一条细线相连。
接下来 $n-1$ 行，每行包含 $2$ 个正整数 $u,v$，表示现在的饰品中小星星 $u$ 和 $v$ 通过细线连了起来。保证这些小星星通过细线可以串在一起。
输出格式：
输出共 $1$ 行，包含一个整数表示可能的对应方式的数量。
如果不存在可行的对应方式则输出
0。数据范围：
对于 $100\%$ 的数据，$n\leq 17$，$m\leq \frac 12n(n-1)$。
子集反演+dp+容斥计数题。
题目的意思其实是：
给定一棵 $n$ 个结点的树 $T$ 和一个 $n$ 个结点的无向图 $G=(V,E)$
要求给树上的结点编号使得编号是一个 $1\sim n$ 的排列，并且任意 $(u,v) \in T$ 有 $(u,v) \in E$ 。
在本题中直接状压是过不了的，因为复杂度是 $\mathcal{O}(n^3\times 3^n)$ 的
因此考虑设 $f_{i,j}$ 表示结点 $i$ 编号为 $j$ ， $i$ 所在子树的方案数。
但是不记录 $i$ 所在子树的编号状况，可能存在重复编号的情况，因此考虑容斥。
我们可以先枚举一个集合 $S = [n]$ （即 $S \subseteq \{1,2,\cdots,n\}$ ），然后钦定选择的结点必须属于 $S$
则总方案数为
其中 $|N(S)|$ 指方案数，我们可以在 $\mathcal{O}(n^3)$ 的复杂度内完成。
证明： 咕咕咕。
时间复杂度 $\mathcal{O}(n^32^n)$
代码：（不知道为什么题目不用取模）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(20))
bitset<N> vis;
int n,m,tot,res,pos=1,c[N],f[N][N],g[N][N],head[N];
struct Edge{ int u,v,next; }e[N*2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u]=pos; }
void dfs(int u,int fa)
{
for(int i=1; i<=tot; i++) f[u][c[i]] = 1;
for(int i=head[u],sum; i; i=e[i].next)
{
int v = e[i].v;
if(v == fa) continue; dfs(e[i].v,u);
for(int j=1; j<=tot; j++)
{
int x = c[j], y; sum = 0;
for(int k=1; k<=tot; k++)
g[x][y = c[k]] ? (sum += f[v][y]) : 0;
f[u][x] *= sum;
}
}
}
void work()
{
tot = 0;
for(int i=1; i<=n; i++) if(vis[i]) c[++tot] = i;
dfs(1,0);
for(int i=1; i<=tot; i++)
res += (((n - tot) & 1) ? -f[1][c[i]] : f[1][c[i]]);
}
void solve(int u)
{
if(u == n + 1) return work();
vis[u] = 0; solve(u+1); vis[u] = 1; solve(u+1);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++)
{ cin >> u >> v; g[u][v] = g[v][u] = 1; }
for(int i=1,u,v; i<n; i++)
{ cin >> u >> v; addEdge(u,v); addEdge(v,u); }
solve(1); cout << res << '\n';
return 0;
}
