BZOJ 4455: [Zjoi2016]小星星 容斥原理+树形DP

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 18
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,edges;
int del[N],con[N][N],hd[N],to[N<<1],nex[N<<1];
ll dp[N][N];
void add(int u,int v)
{
    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
int count(int x)
{
    memset(del,0,sizeof(del));
    int cn=0,re=1,sz=0;
    for(;x;x>>=1,++re)  if(x&1) del[re]=1,++sz;
    return sz;
}
void dfs(int x,int ff)
{
    for(int i=1;i<=n;++i) if(!del[i]) dp[x][i]=1;
    for(int i=hd[x];i;i=nex[i])
    {
        int y=to[i];
        if(y==ff) continue;
        dfs(y,x);
        for(int j=1;j<=n;++j)
        {
            if(del[j]) continue;
            ll sum=0;
            for(int k=1;k<=n;++k)
            {
                if(del[k]||!con[j][k]) continue;
                sum+=dp[y][k];
            }
            dp[x][j]*=sum;
        }
    }
}
int main()
{
    // setIO("input");
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y),con[x][y]=con[y][x]=1;
    }
    for(i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    ll ans=0;
    for(i=0;i<(1<<n);++i)
    {
        int id=count(i);
        dfs(1,0);
        ll sum=0ll;
        for(j=1;j<=n;++j) if(!del[j]) sum+=dp[1][j];
        if(id&1) ans-=sum;
        else ans+=sum;
    }
    printf("%lld\n",ans);
    return 0;
}