标签:子集反演,动态规划

[ZJOI2016]小星星

题目描述

小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星，用 \(m\) 条彩色的细线串了起来，每条细线连着两颗小星星。

有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。

对于 \(100\%\) 的数据，\(n\leq 17\)，\(m\leq \frac 12n(n-1)\)。

思路点拨

在这之前,你需要知道子集反演的一种形式.我们定义 \(f(S)\) 表示集合刚好为 \(S\) 的答案; \(g(S)\) 表示 \(S\) 的所有子集的答案之和.如果 \(g(A)=\sum_{B\subseteq A} f(B)\) ,那么

\[f(A)=\sum_{B\subseteq A} (-1) ^{|A|-|B|}g(B) \]

回到这道题目,由于给树上节点编号的限制是一个排列,这不好解,所以我们可以子集反演变成可以给树上节点随便编号,只要使用地编号在集合 \(S\) 内就可以了.那么我们先枚举集合 \(S\) ,剩下的部分交给树形dp .

我们定义状态 \(f_{i,j}\) 表示在节点 \(i\) 的子树内, \(i\) 的编号是 \(j\) 的方案数.那么考虑转移,我们枚举 \(i\) 的儿子节点以及儿子节点的编号 \(k\) ,如果 \(j,k\) 之间有连边,就可以转移.写成公式就是:

\[f_{i,j}=\prod_{v \in son}\sum_{k=1}^{n} f_{v,k}[k \in S][j,k在图上有连边] \]

容易看出这是 \(O(n^3)\) 的.

时空复杂度计算:时间 \(O(2^n n^3)\) ,空间 \(O(n^3)\) .

\(code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=18;
int n,m;
bool vis[MAXN][MAXN];
vector<int> e[MAXN];
int f[MAXN][MAXN];
int s[MAXN],top;
void dfs(int x,int dad){
	for(int i=1;i<=top;i++)
		f[x][s[i]]=1;
	for(int i=0;i<e[x].size();i++){
		int to=e[x][i];
		if(to==dad) continue;
		dfs(to,x);
		for(int i=1;i<=top;i++){
			int cnt=0;
			for(int j=1;j<=top;j++)
				if(vis[s[i]][s[j]])
					cnt+=f[to][s[j]];
			f[x][s[i]]*=cnt;
		}
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		vis[u][v]=vis[v][u]=1;
	}
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	int ans=0;
	for(int i=1;i<(1<<n);i++){
		memset(f,0,sizeof(f));
		top=0;
		for(int j=0;j<n;j++)
			if(i&(1<<j))
				s[++top]=j+1;
		dfs(1,-1);
		int cnt=0;
		for(int i=1;i<=top;i++)
			cnt+=f[1][s[i]];
		if((n-top)&1) ans-=cnt;
		else ans+=cnt;
	}
	cout<<ans;
	return 0;
}