bzoj4455【ZJOI2016】小星星

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=4455

　　　给一张图和该图的一棵生成树，求可能的编号方案数

sol  ：dalao教导我们，看到计数想容斥

　　　考虑对点i标号，O(2^n)枚举可以标的顶点，然后进行树形dp

　　　f[i][j]表示点i标j号的方案数，容斥一发即可

　　　最后答案为∑f[1][i]，记得开longlong

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

using namespace std;

const int Mx=;

int n,m,cnt,a[Mx],map[Mx][Mx];

long long ans,f[Mx][Mx];

int tot,head[Mx],nxt[Mx],ver[Mx];

void add(int x,int y)

{

    nxt[++tot]=head[x];

    ver[tot]=y;

    head[x]=tot;

}

void dp(int x,int fa)

{

    for(int i=head[x];i;i=nxt[i])

    {

        int y=ver[i];

        if(y!=fa) dp(y,x);

    }

    for(int i=;i<=cnt;i++)

    {

        f[x][i]=;

        for(int j=head[x];j;j=nxt[j])

        {

            int y=ver[j]; long long t=;

            if(y!=fa)

            {

                for(int k=;k<=cnt;k++)

                    if(map[a[i]][a[k]])

                        t+=f[y][k];

                f[x][i]*=t;

            }

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x,y;i<=m;i++)

        scanf("%d%d",&x,&y),

        map[x][y]=map[y][x]=;

    for(int i=,x,y;i<n;i++)

        scanf("%d%d",&x,&y),

        add(x,y),add(y,x);

    for(int i=;i<(<<n);i++)

    {

        cnt=;long long t=;

        for(int j=;j<=n;j++)

            if((i>>(j-))&) a[++cnt]=j;

        dp(,);

        for(int j=;j<=cnt;j++) t+=f[][j];

        ans+=t*(long long) (pow(-,n-cnt));

    }

    printf("%lld\n",ans);

    return ;

}