洛谷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\)

则总方案数为 \[ \sum_{S \subseteq[n]}(-1)^{\left(n-|S|\right)}|N(S)| \tag{1} \] 其中 \(|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;
}