dp[i][j]表示以i为根，且i在原图上对应的点为点j的方案数
可能多个点会对应到原图中的一个点，所以要容斥处理一下
枚举都对应到了哪些点
dp转移方程为 dp[u][j]=π(v∈son[i]）∑（k∈adj[j]）dp[v][k]
子树间方案数是乘起来啊qaq
然后就是容斥了
bin数组是2^i
#include#include #include #include #include #include #include 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