题意: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 ;
}
05-19 08:41