Bzoj4455--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。

-----------------------------------------此后一千里------------------------------------------

很巧妙的一个容斥原理。

考虑设置状态为f[S][i][j]，树上第i个点对应图上第j个点且i所在子树对应图中集合为S的方案数。

那么答案就是sigma{f[全集][1][j]}

直接dp会套一个子集枚举，所以我们枚举S，去容斥出答案，那么我们就可以不在意点对集合一一对应，那么状态就很好转移了。

因为我们只要让它是一个合法转移就可以了，然后容斥部分也很简单，偶加奇减就可以了

代码：

/*
Lelouch vi Britannia here commands you , all of you , die !
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define low(x) ((x)&(-(x)))
#define LL long long
#define eps 1e-9
using namespace std;

#define int int
inline int Max(int a,int b) {return a>b?a:b;}
inline int Min(int a,int b) {return a<b?a:b;}
inline int Abs(int a) {return a>0?a:-a;}
inline int Sqr(int a) {return a*a;}
#undef int

#define MAXN 20

struct edge{
    int to,next;
}e[MAXN*2];int head[MAXN],cnt;
inline void Insert(int a,int b) {
    e[++cnt].next=head[a];head[a]=cnt;e[cnt].to=b;
    e[++cnt].next=head[b];head[b]=cnt;e[cnt].to=a;
}

int n,m,tot,s[MAXN];
int mp[MAXN][MAXN];LL dp[MAXN][MAXN],ans;

void Tree_dp(int v,int fa) {
    for(int i=head[v];i;i=e[i].next) 
        if(e[i].to!=fa) Tree_dp(e[i].to,v);
    for(int i=1;i<=tot;i++) {
        dp[v][s[i]]=1;
        for(int j=head[v];j;j=e[j].next) {
            if(e[j].to==fa) continue;
            LL tmp=0;
            for(int k=1;k<=tot;k++) 
                if(mp[s[i]][s[k]]) 
                    tmp+=dp[e[j].to][s[k]];
            dp[v][s[i]]*=tmp;
            if(!tmp) break;
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int a,b,i=1;i<=m;i++) {
        scanf("%d%d",&a,&b);
        mp[a][b]=mp[b][a]=1;
    }
    for(int a,b,i=1;i<n;i++) {
        scanf("%d%d",&a,&b);
        Insert(a,b);
    }
    int ful=1<<n;
    for(int i=1;i<ful;i++) {
        tot=0;
        for(int j=0;j<n;j++) if(i>>j&1) s[++tot]=j+1;
        Tree_dp(1,0);
        for(int j=1;j<=tot;j++) 
            ans+=((n-tot)&1?-1:1)*dp[1][s[j]];
    }
    cout<<ans<<endl;
    return 0;
}
/*
Hmhmhmhm . That's right , I am killer.
*/

View Code