BZOJ 4455: [Zjoi2016]小星星 [容斥原理 树形DP]

4455: [Zjoi2016]小星星

题意：一个图删掉一些边形成一棵树，告诉你图和树的样子，求让图上的点和树上的点对应起来有多少方案

---

看了很多题解又想了一段时间，感觉题解都没有很深入，现在大致有了自己的想法吧



如果直接上树形DP的话，必须要保存当前子树对应了图上的点的集合才行，要不然做不到1对1.但这样复杂度就炸掉了至少需要\(3^n\)枚举子集



我们可以用容斥原理来弱化这个限制，使得允许多对1

\[树上n个点对应图上n个点的方案数\ = \\
\]

\[n个点对应\le n个点\ -\ n个点对应\le n-1个点\ + n个点对应\le n-2个点\ ...
\]

对应\(\le i\)个点的方案数很好求啊，没有了1对1的限制，直接枚举i个点的集合树形DP就可以了\(O(n^3)\)

总的复杂度\(O(n^32^n)\)，貌似还需要卡一下常



再说一点，这里没有必要想之前\(\ge k\)的容斥原理题一样乘上一个组合数去掉统计方案数时重复了，因为n是全部

```cpp
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=50;
inline int read(){
char c=getchar();int x=0,f=1;
while(c'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&cint n, m, x, y, g[N][N], a[N], p;

struct edge{int v, ne;}e[N];

int cnt, h[N];

inline void ins(int u, int v) {

e[++cnt]=(edge){v, h[u]}; h[u]=cnt;

e[++cnt]=(edge){u, h[v]}; h[v]=cnt;

}

ll f[N][N];

void dfs(int u, int fa) {

for(int j=1; j<=p; j++) f[u][j]=1;

for(int i=h[u];i;i=e[i].ne) if(e[i].v != fa) {

int v=e[i].v;

dfs(v, u);

for(int j=1; j<=p; j++) {

ll t=0;

for(int k=1; k<=p; k++) if(g[a[j]][a[k]]) t += f[v][k];

f[u][j] *= t;

}

}

}

int main() {

freopen("in","r",stdin);

n=read(); m=read();

for(int i=1; i<=m; i++) x=read(), y=read(), g[x][y]=g[y][x]=1;

for(int i=1; i<n; i++) ins(read(), read());

int All=1<<n;

ll ans=0;

for(int s=1; s<All; s++) {

p=0; ll t=0;

for(int i=0; i<n; i++) if(s&(1<<i)) a[++p]=i+1;

dfs(1, 0);

for(int i=1; i<=p; i++) t+=f[1][i];

if((n-p)&1) ans -= t;

else ans += t;

}

printf("%lld\n",ans);

}