[ZJOI2016] 小星星
题目描述
小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星，用 \(m\) 条彩色的细线串了起来，每条细线连着两颗小星星。
有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。
只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。
输入格式
第一行包含 \(2\) 个正整数 \(n,m\)，表示原来的饰品中小星星的个数和细线的条数。
接下来 \(m\) 行，每行包含 \(2\) 个正整数 \(u,v\)，表示原来的饰品中小星星 \(u\) 和 \(v\) 通过细线连了起来。这里的小星星从 \(1\) 开始标号。保证 \(u\neq v\)，且每对小星星之间最多只有一条细线相连。
接下来 \(n-1\) 行，每行包含 \(2\) 个正整数 \(u,v\)，表示现在的饰品中小星星 \(u\) 和 \(v\) 通过细线连了起来。保证这些小星星通过细线可以串在一起。
输出格式
输出共 \(1\) 行，包含一个整数表示可能的对应方式的数量。
如果不存在可行的对应方式则输出 0。
样例 #1
样例输入 #1
4 3
1 2
1 3
1 4
4 1
4 2
4 3
样例输出 #1
6
提示
对于 \(100\%\) 的数据，\(n\leq 17\)，\(m\leq \frac 12n(n-1)\)。
零.忘了
一.思路
首先，这道题是给你一个图和一个树，问你树上对应序号到图上的点有边相连的方案数?
- 看到n$≤$17我们先考虑暴力
对于每个树上的点与点和连边都\(O(n)\)枚举图上的点和边，如果对应点有连边就方案数\(+1\),总复杂度\(O(n! \times n)\)
- 考虑状压+容斥
给出一个图，给出一棵树，你需要把树上的点映射到图上，两个点不能映射到同一个点。
要求若两个点在树上有一条边连着，那么映射到的点在原图上也要有一条边，求方案数。
如果考虑树上两个点不能映射到图上同一个点，发现状态比较难设计，（并且会T）? 具体方法就是\(dp[i][j][s]\) 树上i点对应图上j点时，\(i\)の子树情况为\(s\)时の总方案数，但是时间主要消耗在集合の枚举上
有第三维是因为题目要求序号是对应的?
那么我们需要考虑容斥来减少枚举集合の时间
先假设\(dp[i][j]\)是树上i点对应图上j点时，\(i\)の子树の总方案数
假设树上的点可以对应图上所有点
那么
对于 树上\(i\)和\(i\)De儿子\(j\)の连边 对应图上\(o\)和\(p\)的时候，如果\(o\)和\(p\)存在连边，那么就把\(dp[j][p]\)加到\(sum\)中(统计以\(i\)为根的子树の方案数) 根据乘法原理，\(dp[i][o]\)再乘上子树里下一层の方案数\(sum\)即可
然后考虑去掉重复の情况
这时树上的点可以对应图上所有点，考虑去掉树上两个点对应图上一个点的重复情况
比如有3个点，1映射到2，2映射到2，3映射到1。
只有图上\(3\)没有被映射到
所以减去有一个点没有被映射到の情况
最后减去了\((1,2,2),(1,3,3),(1,1,2),(1,1,3),(2,2,1),(2,2,3),......\)等情况
但是如果有\(2\)个点没有被映射到呢
比如有3个点，1映射到2，2映射到2，3映射到2。
发现1没有被映射到的时候减掉一次，3没有被映射到的时候被减掉一次，所以加上这次就行了
当然，根据子集反演，我们容易得到容斥系数\((-1)^{n-|T|}\)
所以答案即为规定全集-规定不选1个+规定不选2个...。
我们可以二进制枚举，枚举哪些图上的点参与dp，按照容斥原理加减，这样就可以算出答案，复杂度为\(O(2^n n^3)\)
初始化：\(dp[x][i]=1\)，因为若\(x\)的子树中只有\(x\)，那么\(x\)可以对应到原图任意一个点。
图上映射的点有奇数个的时候加起来，偶数个的时候减去就行力
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void Write(int x){
if(x>9) Write(x/10);
putchar(x%10+'0');
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
Write(x);
putchar('\n');
}
}
using namespace Testify;
const int N=150;
int head[N],nxt[N<<1],to[N<<1],tot(0);
inline void add(int x,int y){
to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,m,dp[N][N];
bool mapp[N][N]/*树上第i个点对应图上第j点の方案数*/,Stasis[N];
inline void pre(int s){
memset(Stasis,0,sizeof(Stasis));
int cnt=0;
while(s){
cnt++;
if(s&1){
Stasis[cnt]=true;
}
s>>=1;
}
}
inline int numcount(int s){
int USAO(0);
while(s){
USAO++;
s-=(s&(-s));
}
return USAO;
}
inline void dfs(int now,int fa){
for(register int i=1;i<=n;i++){
dp[now][i]=1;
}
for(register int i=head[now];i;i=nxt[i]){//树
int y=to[i];
if(y==fa) continue;
dfs(y,now);
//遍历到叶子节点再合并
for(register int j=1;j<=n;j++){
if(!Stasis[j]) continue;//如果j在图里不选
int sum(0);
for(register int k=1;k<=n;k++){
if(!Stasis[k] || !mapp[j][k]) continue;//如果k在图里不选 或者 j到k没有连边
sum+=dp[y][k];//树上的nowの子节点y 在图上对应的点为 k
}
dp[now][j]*=sum;
}
}
}
signed main(){
system("title IZANA");
n=read(),m=read();
for(register int i=1;i<=m;i++){
int a=read(),b=read();
mapp[a][b]=true,mapp[b][a]=true;
}
for(register int i=1;i<n;i++){
int a=read(),b=read();
add(a,b),add(b,a);
}
int Tempestissimo(0);
for(register int i=0;i<(1<<n);i++){
//iの状态树对应图上的哪些点参与dp????????
//如果参与点有奇数个就容斥-
//如果参与点有偶数个就容斥+
pre(i);
dfs(1,0);
int sum(0);
for(register int j=1;j<=n;j++){
sum+=dp[1][j];
//Tempestissimo加上所有以1为根の1在树上所有映射的点の情况
}
if(numcount(i)&1){
Tempestissimo-=sum;
}
else{
Tempestissimo+=sum;
}
}
write(abs(Tempestissimo));
cerr<<"哪里功夫高";
return 0;
}