bzoj 4455 [Zjoi2016]小星星

Description

小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有n颗小星星，用m条彩色的细线串了起来，每条细
线连着两颗小星星。有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了n?1条细线，但
通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小Y找到了这个饰品的设
计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，
那么要求对应的小星星原来的图纸上也有细线相连。小Y想知道有多少种可能的对应方式。只有你告诉了她正确的
答案，她才会把小饰品做为礼物送给你呢。

Input

第一行包含个2正整数n,m，表示原来的饰品中小星星的个数和细线的条数。
接下来m行，每行包含2个正整数u,v，表示原来的饰品中小星星u和v通过细线连了起来。
这里的小星星从1开始标号。保证u≠v，且每对小星星之间最多只有一条细线相连。
接下来n-1行，每行包含个2正整数u,v，表示现在的饰品中小星星u和v通过细线连了起来。
保证这些小星星通过细线可以串在一起。
n<=17,m<=n*(n-1)/2

Output

输出共1行，包含一个整数表示可能的对应方式的数量。
如果不存在可行的对应方式则输出0。

Sample Input

4 3

1 2

1 3

1 4

4 1

4 2

4 3

Sample Output

6

题解

用f[i][j]表示点i对应点j的方案数。。。这样就会出现一个点匹配多个点的问题了。但是如果这样的话因为它合法的对应方案一定是n个对n个的，如果原图中的一个点被新图中的两个点匹配到了，那原图里面一定有一个点没有被新图中的任何点匹配。

那实际上不合法的状态可以被用两种方法表示：第一个是至少有一个点匹配了多个点，第二个是至少有一个点没有被匹配到。这样的话就可以发现强制某些点不选就可以构造出需要去掉的不合法情况，然后就用总方案-至少一个点没有被选的方案+至少两个点没有被选的方案…这样容斥一下就可以了。

#include <cstdio>
#include <cstring>
using namespace std;
long long ans, f[20][20];
int n, m, x, y, v[20];
struct gra {
    int tot, st[20];
    struct edge {
        int to, next;
    }e[500];
    void add(int x, int y) {
        e[++tot].next = st[x];
        e[tot].to = y, st[x] = tot;
    }
}g, t;
void dfs(int now, int pre) {
    for (int i = 1; i <= n; ++i)
        if (!v[i]) f[now][i] = 1;
    for (int i = t.st[now]; i; i = t.e[i].next)
        if (t.e[i].to != pre) {
            int to = t.e[i].to; dfs(to, now);
            for (int j = 1; j <= n; ++j) {
                long long sum = 0;
                for (int k = g.st[j]; k; k = g.e[k].next)
                    sum += f[to][g.e[k].to];
                f[now][j] *= sum;
            }
        }
}
long long solve() {
    long long ans = 0;
    memset(f, 0, sizeof f);
    dfs(1, 0);
    for (int i = 1; i <= n; ++i)
        ans += f[1][i];
    return ans;
}
void work(int now, int cnt) {
    if (now > n) {
        ans += ((cnt & 1) ? -1ll : 1ll) * solve();
        return;
    }
    for (int i = 0; i <= 1; ++i)
        v[now] = i, work(now + 1, cnt + i), v[now] = 0;
}
main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &x, &y), g.add(x, y), g.add(y, x);
    for (int j = 1; j < n; ++j)
        scanf("%d%d", &x, &y), t.add(x, y), t.add(y, x);
    work(1, 0);
    printf("%lld\n", ans);
}