题目描述
题解
大意：给出一张n个点n+x条边的无向连通图，x很小，求出这个图上最大独立集的方案数。
感觉就是NOIP保卫王国那题的加强版吧。
暴力的话，我们可以考虑在图上随便找一颗生成树，然后把非树边连接的点设置为关键点，然后2^x枚举这些点的选择情况，每次做一遍树形dp就好了。
如果做到这里，那么可以自然而然的想到一个优化：虚树。
就是发现在虚树上的非关键点部分的转移相似，所以我们可以预处理出这些东西来。
我们设f[i][0/1]表示i点的所有不包含关键点的子树的答案。
对于关键点到关键点的转移，我们可以设k[i][0/1][0/1]表示关键点i点到i点的第一个关键点祖先的儿子处i点和那个儿子的选择情况的方案数。
这个直接从i点向上跳，边跳边统计答案就可以算出来了。
注意虚树上的LCA点也要标为关键点。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define N 110009
using namespace std;
typedef long long ll;
const int mod=;
vector<int>vec[N];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct node{int u,v;}ed[];
ll k[N][][],g[N][],f[N][],ans;
int tot,head[N],dfn[N],p[][N],deep[N],a[N],ttt,n,m,st[N],top;
bool vis[N],dy1[N],dy0[N],tag[N];
struct edge{int n,to;}e[N<<];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
inline void add2(int u,int v){tag[u]=;tag[v]=;vec[u].push_back(v);}////!!!!!!!!!
void dfs(int u,int fa){
dfn[u]=++dfn[];vis[u]=;
for(int i=;(<<i)<=deep[u];++i)p[i][u]=p[i-][p[i-][u]];
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
if(!vis[v]){deep[v]=deep[u]+;p[][v]=u;dfs(v,u);}
else{a[++a[]]=u;a[++a[]]=v;ed[++ttt]=node{u,v};}
}
}
inline bool cmp(int a,int b){return dfn[a]<dfn[b];}
inline int getlca(int a,int b){
if(deep[a]<deep[b])swap(a,b);
for(int i=;i>=;--i)if(deep[a]-(<<i)>=deep[b])a=p[i][a];
if(a==b)return a;
for(int i=;i>=;--i)if(p[i][a]!=p[i][b])a=p[i][a],b=p[i][b];
return p[][a];
}
void predp(int u,int jin){
f[u][]=f[u][]=;tag[u]=;
for(int i=head[u];i;i=e[i].n){
int v=e[i].to;
if(p[][v]!=u||v==jin||tag[v])continue;
predp(v,jin);
f[u][]=f[u][]*(f[v][]+f[v][])%mod;
f[u][]=f[u][]*f[v][]%mod;
}
}
inline void getnum(int x,int y){
k[x][][]=k[x][][]=;
for(int i=x;p[][i]!=y;i=p[][i]){
predp(p[][i],i);
ll xx=k[x][][],yy=k[x][][];
k[x][][]=f[p[][i]][]*(k[x][][]+k[x][][])%mod;
k[x][][]=f[p[][i]][]*xx%mod;
k[x][][]=f[p[][i]][]*(k[x][][]+k[x][][])%mod;
k[x][][]=f[p[][i]][]*yy%mod;
}
}
void prework(int u){
for(int i=;i<vec[u].size();++i){
int v=vec[u][i];
prework(v);getnum(v,u);
}
f[u][]=f[u][]=;
for(int i=head[u];i;i=e[i].n){
int v=e[i].to;
if(p[][v]!=u||tag[v])continue;
predp(v,);
f[u][]=f[u][]*(f[v][]+f[v][])%mod;
f[u][]=f[u][]*f[v][]%mod;
}
}
void dp(int u){
g[u][]=f[u][];g[u][]=f[u][];
if(dy1[u])g[u][]=;if(dy0[u])g[u][]=;
for(int i=;i<vec[u].size();++i){
int v=vec[u][i];
dp(v);
ll k0=(k[v][][]*g[v][]%mod+k[v][][]*g[v][]%mod)%mod,k1=(k[v][][]*g[v][]%mod+k[v][][]*g[v][]%mod)%mod;
g[u][]=g[u][]*(k0+k1)%mod;g[u][]=g[u][]*k0%mod;
}
}
int main(){
n=rd();m=rd();int u,v;
for(int i=;i<=m;++i){
u=rd();v=rd();
add(u,v);add(v,u);
}
dfs(,);sort(a+,a+a[]+,cmp);
a[]=unique(a+,a+a[]+)-a-;
st[top=]=;
for(int i=;i<=a[];++i){
tag[a[i]]=;
if(a[i]==st[top])continue;
int lca=getlca(st[top],a[i]);
if(lca==st[top]){st[++top]=a[i];continue;}
while(top>){
int x=st[top],y=st[top-];
if(dfn[lca]>=dfn[y]){add2(lca,x);top--;break;}
add2(y,x);top--;
}
if(st[top]!=lca)st[++top]=lca;
if(st[top]!=a[i])st[++top]=a[i];
}
while(top>)add2(st[top-],st[top]),top--;
prework();
for(int i=;i<(<<a[]);++i){
for(int j=;j<=a[];++j)if(i&(<<j-))dy1[a[j]]=,dy0[a[j]]=;else dy0[a[j]]=,dy1[a[j]]=;
bool tagg=;
for(int j=;j<=ttt;++j){
int u=ed[j].u,v=ed[j].v;
if(dy1[u]&&dy1[v]){tagg=;break;}
}
if(tagg)continue;
dp();
(ans+=g[][]+g[][])%=mod;
}
cout<<ans;
return ;
}