P3349 小星星 题解
wind_whisper
2021-10-27 20:36:45
# 前言
看题解区各位大佬都是用的神仙的容斥 dp ，可是本蒟蒻根本想不到啊... qwq
我写的时候用的是一种和本题大部分做法都不同的思路，虽然时间复杂度并没有正解优越，但是思考起来和代码实现都变得更加简单.
（第一次发题解，希望管理员通过！ OvO ）
# 解析
直接考虑朴素 dp .
$dp_{i,s,j}$ 表示 $i$ 的子树内，已经被对应的节点状态为 $s$ ，$i$ 对应的节点是 $j$ 的对应方案数.
当 $x$ 的子树内又纳入了一个新儿子的时候，就可以枚举**交集为 $0$ 的 $u$ 和 $v$ ,以及两个集合中有连边的 $p$ 和 $q$ ,** 进行转移：
$$ dp_{x,u|v,q}+=dp_{son,u,p}\times dp_{x,v,q} $$
然而这么搞，即使加上枚举子集的优化，也是会 T 飞的.
仔细想想，这里有很多的 dp 本身显然会是不合法的，我们进行了太多无用的转移.
考虑如何优化.
记 $siz_i$ 为 $i$ 的子树大小.
显然，如果 $u$ 的二进制表示的1的个数不等于 $siz_{son}$ ，那么 $dp_{son,u,...}$ 必然是不合法的，没有必要从那里进行转移，我们只需要**枚举二进制表示下1的个数等于 $siz_{son}$ 的 $u$ 进行转移即可**.
同理，若 $x$ 在**加入 $son$ 前**的子树大小为 $siz_x$ ，我们也只需要枚举二进制表示下 $1$ 的个数等于 $siz_x$ 的 $v$ 进行转移即可.
和[有线电视网（树上背包）](https://www.luogu.com.cn/problem/P1273)的实现过程有异曲同工之妙.
最后的答案就是：
$$\sum\limits_{i=1}^ndp_{1,2^n-1,i}$$
具体实现上，为了后面枚举的方便，我们可以预处理出来二进制表示下 $1$ 的个数为 $k$ 的数有哪些.
于是，仅仅加入了这么一个小清新且简单易懂的优化之后，你发现你已经切掉了这道紫题.
本人的代码完全没有卡过常，不吸氧会T一个点，吸氧后可以通过.
~~但是现在CSP NOIP都有氧气了，吸氧又有什么关系呢.~~
~~毕竟这个方法可比容斥好像多了啊!~~
代码写起来也很舒适，不伤肝.
# 代码
（有注释哦！）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
const int N=2e5+100;
const double eps=1e-6;
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
struct node{
int to,nxt;
}p[38];
int fi[N],cnt;
inline void addline(int x,int y){
p[++cnt]=(node){y,fi[x]};fi[x]=cnt;
return;
}
int st[18][N],num[18],mi[18];
int siz[18];
ll dp[18][N][18];
bool vis[18][18];
void dfs(int x,int f){
siz[x]=1;
for(int i=0;i<n;i++) dp[x][mi[i]][i+1]=1;//一开始x对应任何一个节点的方案数都为1
for(int i=fi[x];~i;i=p[i].nxt){
int to=p[i].to;
if(to==f) continue;
dfs(to,x);
int a=siz[x],b=siz[to];
for(int j=1;j<=num[a];j++){//枚举二进制下有siz[x]个1的状态
int u=st[a][j];
for(int k=1;k<=num[b];k++){//枚举二进制下有siz[son]个1的状态
int v=st[b][k];
if(u&v) continue;//如果有交集，不能产生贡献
for(int p=1;p<=n;p++){
if(!dp[to][v][p]) continue;//如果dp[to][v][p]=0,必然不会再转移产生贡献
if((v&mi[p-1])==0) continue;//枚举的p必须是v集合内的元素
for(int q=1;q<=n;q++){
if(!vis[p][q]) continue;//p和q之间必须有连边
if((u&mi[q-1])==0) continue;//枚举的q必须是u集合内的元素
dp[x][u|v][q]+=dp[to][v][p]*dp[x][u][q];
}
}
}
}
siz[x]+=siz[to];
}
return;
}
inline int calc(int x){
int res=0;
while(x){
res+=x&1;x>>=1;
}
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
memset(fi,-1,sizeof(fi));cnt=-1;
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
vis[x][y]=vis[y][x]=1;
}
for(int i=1;i<n;i++){
int x=read(),y=read();
addline(x,y);addline(y,x);
}
mi[0]=1;
for(int i=1;i<=n;i++) mi[i]=mi[i-1]<<1;
for(int i=0;i<mi[n];i++){//预处理二进制下有k个1的数有哪些
int o=calc(i);
st[o][++num[o]]=i;
}
dfs(1,0);
ll res=0;
for(int i=1;i<=n;i++){//统计答案
res+=dp[1][mi[n]-1][i];
}
printf("%lld\n",res);
return 0;
}
/*
*/
```
(这么简单的做法不点个赞再走吗 awa )