Description

小Y是一个心灵手巧的女孩子,她喜欢手工制作一些小饰品。她有n颗小星星,用m条彩色的细线串了起来,每条细
线连着两颗小星星。有一天她发现,她的饰品被破坏了,很多细线都被拆掉了。这个饰品只剩下了n?1条细线,但
通过这些细线,这颗小星星还是被串在一起,也就是这些小星星通过这些细线形成了树。小Y找到了这个饰品的设
计图纸,她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连,
那么要求对应的小星星原来的图纸上也有细线相连。小Y想知道有多少种可能的对应方式。只有你告诉了她正确的
答案,她才会把小饰品做为礼物送给你呢。

Input

第一行包含个2正整数n,m,表示原来的饰品中小星星的个数和细线的条数。
接下来m行,每行包含2个正整数u,v,表示原来的饰品中小星星u和v通过细线连了起来。
这里的小星星从1开始标号。保证u≠v,且每对小星星之间最多只有一条细线相连。
接下来n-1行,每行包含个2正整数u,v,表示现在的饰品中小星星u和v通过细线连了起来。
保证这些小星星通过细线可以串在一起。
n<=17,m<=n*(n-1)/2
 

Output

输出共1行,包含一个整数表示可能的对应方式的数量。
如果不存在可行的对应方式则输出0。

Sample Input

4 3
1 2
1 3
1 4
4 1
4 2
4 3

Sample Output

6
 
设A(i)表示包含了原图上点i的映射集合,则答案集合为A(1)、A(2)、A(3)……、A(n)的交集,因为|A(1)∩A(2)∩……∩A(n)|=|A(1)υA(2)υ……υA(n)|-|A(2)υ----υA(n)|+……
所以我们枚举2^n-1个并集,用树上DP计算出并集的大小,容斥一下就能得到|A(1)∩A(2)∩……∩A(n)|了。
树上DP可以设f[x][y]表示以x为根的子树,x的映射元素是y的方案数,枚举子节点的映射元素然后转移了。
时间复杂度为O(2^N*N^3)。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
typedef long long ll;
const int maxn=20;
int n,m,first[maxn],next[maxn<<1],to[maxn<<1],e,w[20][20];
int q[maxn],k;
ll f[20][20];
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
to[++e]=u;next[e]=first[v];first[v]=e;
}
void dp(int x,int fa) {
ren if(to[i]!=fa) dp(to[i],x);
rep(j,1,k) {
f[x][j]=1;
ren if(to[i]!=fa) {
ll res=0;
rep(y,1,k) if(w[q[j]][q[y]]) res+=f[to[i]][y];
f[x][j]*=res;
}
}
}
int main() {
n=read();m=read();
rep(i,1,m) {
int u=read(),v=read();
w[u][v]=w[v][u]=1;
}
rep(i,2,n) AddEdge(read(),read());
ll ans=0;
rep(S,0,(1<<n)-1) {
k=0;ll res=0;
rep(i,0,n-1) if(S>>i&1) q[++k]=i+1;
dp(1,0);rep(i,1,k) res+=f[1][i];
if(!(n-k&1)) ans+=res; else ans-=res;
}
printf("%lld\n",ans);
return 0;
}

  

最新文章

  1. 2014年年度工作总结--IT狂人实录
  2. Android 热修复技术(1)---原理
  3. BZOJ3331: [BeiJing2013]压力
  4. SSL、OPENSSL、SSH、OPENSSH
  5. 【java消息格式化】使用MessageFormat进行消息格式化
  6. Codeforces Round #379 (Div. 2) D. Anton and Chess 水题
  7. android和struts2实现android文件上传
  8. iOS_ScrollView的自己主动布局
  9. TensorFlow for R
  10. Quartz学习——Spring和Quartz集成详解(三)
  11. 将简单Excel表格显示到DataGridView中
  12. 关于我空间那篇名为《JavaScript axError:Unexpected token ILLEGAL 很简单的代码&hellip;&hellip;》的随笔
  13. 树遍历(广度优先 vs 深度优先)
  14. P1035 调和级数
  15. 常用的16个c/c++面试题
  16. Java内存分配机制
  17. 7.6 GRASP原则六: 多态 Polymorphism
  18. 解决Android SDK下载和更新失败问题
  19. 20171114xlVba选定单行记录并打印
  20. Selenium上传文件

热门文章

  1. Jmeter—4 添加断言 判断响应数据是否符合预期
  2. AC日记——阶乘之和 洛谷 P1009(高精度)
  3. SQL 的一些概念问答
  4. OAuth 的权限问题与信息隐忧
  5. HDU4763 - Theme Section(KMP)
  6. hdoj 2955 Robberies
  7. Ubuntu14.04 如何修改/etc/sudoers 和错误修改权限的解决办法
  8. hdu 1205
  9. Python中def的用法
  10. [Uva247][Tarjan求强连通分量][Calling Circles]
  11. python基础教程第二版 第一章
  12. Java集合框架(三)—— List、ArrayList、Vector、Stack
  13. Android 加载GIF图最佳实践
  14. IDEA 热部署设置(JRebel插件激活)
  15. html2canvas将页面内容生成图片
  16. IDEA中Maven项目使用Junit4单元测试的写法
  17. webapi postman 415 错误
  18. Nginx:413 Request Entity Too Large
  19. [django]session设置与获取原理
  20. poj1102