uoj#185 小星星

dp[i][j]表示以i为根，且i在原图上对应的点为点j的方案数

可能多个点会对应到原图中的一个点，所以要容斥处理一下

枚举都对应到了哪些点

dp转移方程为 dp[u][j]=π(v∈son[i]）∑（k∈adj[j]）dp[v][k]

子树间方案数是乘起来啊qaq

然后就是容斥了

bin数组是2^i

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;

const int maxn = 30;

int n,m,cnt;
ll f[maxn][maxn],ans,res;
int a[maxn],bin[maxn];

int h[maxn],size,h1[maxn],size1;
struct E{
    int to,next;
}e[maxn<<5],e1[maxn<<5];
void add(int u,int v){
    e[++size].to=v;
    e[size].next=h[u];
    h[u]=size;
}
void add1(int u,int v){
    e1[++size1].to=v;
    e1[size1].next=h1[u];
    h1[u]=size1;
}

void dfs(int u,int par){
    for(int i=h1[u];i!=-1;i=e1[i].next){
        int v=e1[i].to;
        if(v==par) continue;
        dfs(v,u);
    }
    
    for(int i=1;i<=cnt;i++){
        f[u][a[i]]=1;
    
        for(int j=h1[u];j!=-1;j=e1[j].next){
            int v=e1[j].to;
            ll res=0;
            if(v==par) continue;
            for(int k=h[a[i]];k!=-1;k=e[k].next){
                res+=f[v][e[k].to];
            }
            f[u][a[i]]*=res;
            if(!res) break;
        }
    }
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}

int main(){
    memset(h,-1,sizeof(h));
    memset(h1,-1,sizeof(h1));
    n=read(),m=read();
    bin[0]=1; for(int i=1;i<=n;i++) bin[i]=bin[i-1]<<1;
    int u,v;
    for(int i=1;i<=m;i++){
        u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<n;i++){
        u=read(),v=read();
        add1(u,v),add1(v,u);
    }
    
    for(int i=1;i<(1<<n);i++){
        cnt=0;
        memset(f,0,sizeof(f));
        for(int j=0;j<n;j++){
            if(i&(1<<j)) a[++cnt]=j+1;
        }
        dfs(1,0);
        res=0;
        for(int j=1;j<=cnt;j++) res+=f[1][a[j]];
        if((n-cnt)&1) ans-=res; else ans+=res;
    }
    printf("%lld\n",ans);
    
    return 0;
}