Rockdu's Blog

题目描述

小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有n颗小星星，用m条彩色的细线串了起来，每条细线连着两颗小星星。

有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了n?1条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小Y找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小Y想知道有多少种可能的对应方式。

只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。

输入输出格式

输入格式：

第一行包含个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

输出格式：

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

输入输出样例

4 3
1 2
1 3
1 4
4 1
4 2
4 3

6

说明

题解:JudgeOnline/upload/201603/4455.txt

首先考虑一个最暴力的状态压缩，dp[i][j][mask]表示树上第i个点在图上分配的编号为j，并且对树上的点，已经分配了mask这个状态集合内的标号。这样就变成了给定的树上的一个树形dp，发现mask的转移是需要子集枚举的，总复杂度为O(n^3*3^n)。

这个dp的瓶颈在于子集枚举，发现我们限制了每一个编号只能分配一次。如果不要这个限制呢？

我们考虑枚举用到的编号，显然可以求出此时允许分配重复编号的方案数，用dp[i][j]表示树上i号点分配图上编号为j的方案数直接转移即可。并且通过枚举用到的编号，我们可以求出至少有x个编号被重复分配的方案。把至少变成仅有，只要一遍容斥原理就可以了。复杂度：O(n^3*2^n)

#include<cstdio>
#include<cstring>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 30;
int n, m, mp[maxn][maxn], mxst, u, v;
struct edge {
    int v, next;
}e[maxn << 1];
int head[maxn], cnt, p[maxn], top, id;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}

void Inv(int mask) {
    top = 0, id = 0;
    while(mask) {
        ++id;
        if(mask & 1) p[++top] = id;
        mask >>= 1;
    }
}

LL dp[maxn][maxn], ans[maxn];

void DP(int u, int fa) {
    LL sum = 0;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v; 
        if(v == fa) continue; 
        DP(v, u);
        For(j, 1, top) {
            sum = 0;
            For(k, 1, top) if(mp[p[j]][p[k]]) sum += dp[v][k];
            dp[u][j] *= sum;
        }
    }
}

LL Gans() {
    LL ans = 0;
    For(i, 1, n) For(j, 1, top) dp[i][j] = 1;
    DP(1, 0);For(i, 1, top) ans += dp[1][i];
    return ans;
}

LL A;

int main() {
    scanf("%d%d", &n, &m), mxst = 1 << n;
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d", &u, &v), mp[u][v] = mp[v][u] = 1;
    for(register int i = 1; i < n; ++i)
        scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
    for(register int k = 1; k < mxst; ++k)
        Inv(k), ans[n - top] += Gans();
    for(register int i = 0; i < n; ++i)
        A = A + ((i & 1) ? -1 : 1) * ans[i];
    printf("%lld", A);
    return 0;
}