【HNOI2018】毒瘤
设\(f_{v,0}\)表示\(v\)的子树中\(v\)不选的方案数，\(f_{v,1}\)表示\(v\)选的方案数。
显然
\[f_{v,0}=\prod (f_{sn,0}+f_{sn,1})\\
f_{v,1}=\prod f_{sn,0}
\]
f_{v,1}=\prod f_{sn,0}
\]
我们可以写成矩阵乘法的形式
\[\begin{bmatrix}f_{sn,0}& f_{sn,1}\end{bmatrix}
\begin{bmatrix} f_{v,0}&f_{v,1}\\f_{v,0}& 0 \end{bmatrix}=\begin{bmatrix}f_{v,0}& f_{v,1}\end{bmatrix}
\]
\begin{bmatrix} f_{v,0}&f_{v,1}\\f_{v,0}& 0 \end{bmatrix}=\begin{bmatrix}f_{v,0}& f_{v,1}\end{bmatrix}
\]
然后我们就枚举非树边两端的点选与不选，用动态\(DP\)维护。
设非树边有\(k\)条，暴力枚举复杂度\(O(2^{2k}log^2N)\)。
但是我们发现，每条边只需要枚举其中一个点就好了。如果枚举为不选，那么另一个点就没有限制；如果必选，那么另一个点就不选。复杂度\(O(2^{k}log^2N)\)。
和【SDOI 2017】切树游戏一样要用一个类来处理除法中除\(0\)的情况。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=998244353;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int n,m;
struct road {
int to,next;
}s[N<<1];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
struct edge {
int x,y;
}e[N];
int tot;
int FA[N];
int Getf(int v) {return FA[v]==v?v:FA[v]=Getf(FA[v]);}
int fa[N],size[N],son[N];
int top[N];
struct info {
ll a,z;
info() {a=1,z=0;}
info(int x,int y) {a=x,z=y;}
ll val() {return z?0:a;}
};
info operator *(info x,ll y) {
if(!y) x.z++;
else x.a=x.a*y%mod;
return x;
}
info operator /(info x,ll y) {
if(!y) x.z--;
else x.a=x.a*ksm(y,mod-2)%mod;
return x;
}
struct matrix {
int a[2][2];
void Init() {a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
};
matrix operator *(const matrix &x,const matrix &y) {
matrix tem;
tem.Init();
tem.a[0][0]=(1ll*x.a[0][0]*y.a[0][0]+1ll*x.a[0][1]*y.a[1][0])%mod;
tem.a[0][1]=(1ll*x.a[0][0]*y.a[0][1]+1ll*x.a[0][1]*y.a[1][1])%mod;
tem.a[1][0]=(1ll*x.a[1][0]*y.a[0][0]+1ll*x.a[1][1]*y.a[1][0])%mod;
tem.a[1][1]=(1ll*x.a[1][0]*y.a[0][1]+1ll*x.a[1][1]*y.a[1][1])%mod;
return tem;
}
struct tree {
int l,r;
matrix w;
}tr[N<<2];
void update(int v) {tr[v].w=tr[v<<1|1].w*tr[v<<1].w;}
void build(int v,int l,int r) {
tr[v].l=l,tr[v].r=r;
if(l==r) return ;
int mid=l+r>>1;
build(v<<1,l,mid),build(v<<1|1,mid+1,r);
}
void dfs(int v) {
size[v]=1;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(to==fa[v]) continue ;
fa[to]=v;
dfs(to);
size[v]+=size[to];
if(size[son[v]]<size[to]) son[v]=to;
}
}
matrix query(int v,int l,int r) {
if(l<=tr[v].l&&tr[v].r<=r) return tr[v].w;
int mid=tr[v].l+tr[v].r>>1;
if(r<=mid) return query(v<<1,l,r);
else if(l>mid) return query(v<<1|1,l,r);
else return query(v<<1|1,l,r)*query(v<<1,l,r);
}
int dfn[N],lst[N],id;
int bot[N];
ll t[N];
info G[N][2];
void Modify(int v,int p) {
if(tr[v].l>p||tr[v].r<p) return ;
if(tr[v].l==tr[v].r) {
matrix &w=tr[v].w;
w.a[0][0]=G[lst[p]][0].val(),w.a[0][1]=G[lst[p]][1].val();
w.a[1][0]=G[lst[p]][0].val(),w.a[1][1]=0;
if(~t[lst[p]]) {
w.a[0][t[lst[p]]^1]=w.a[1][t[lst[p]]^1]=0;
}
return ;
}
Modify(v<<1,p),Modify(v<<1|1,p);
update(v);
}
void dfs2(int v,int tp) {
dfn[v]=++id;
lst[id]=v;
top[v]=tp;
bot[v]=v;
if(son[v]) {
dfs2(son[v],tp);
bot[v]=bot[son[v]];
}
G[v][0]=G[v][1]=info(1,0);
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(to==son[v]||to==fa[v]) continue ;
dfs2(to,to);
matrix tem=query(1,dfn[to],dfn[bot[to]]);
G[v][0]=G[v][0]*(tem.a[0][0]+tem.a[0][1]);
G[v][1]=G[v][1]*tem.a[0][0];
}
Modify(1,dfn[v]);
}
int dep;
void Confirm(int v,int flag) {
dep++;
t[v]=flag;
matrix tem;
for(int i=top[v];fa[i];i=top[fa[i]]) {
tem=query(1,dfn[i],dfn[bot[i]]);
G[fa[i]][0]=G[fa[i]][0]/(tem.a[0][0]+tem.a[0][1]);
G[fa[i]][1]=G[fa[i]][1]/tem.a[0][0];
}
Modify(1,dfn[v]);
for(int i=top[v];fa[i];i=top[fa[i]]) {
tem=query(1,dfn[i],dfn[bot[i]]);
G[fa[i]][0]=G[fa[i]][0]*(tem.a[0][0]+tem.a[0][1]);
G[fa[i]][1]=G[fa[i]][1]*tem.a[0][0];
Modify(1,dfn[fa[i]]);
}
}
vector<int>st;
vector<int>E[N];
int ban[N];
ll ans;
vector<int>ea,eb;
void solve(int now) {
if(now==ea.size()) {
matrix tem=query(1,dfn[1],dfn[bot[1]]);
(ans+=tem.a[0][0]+tem.a[0][1])%=mod;
return ;
}
int x=ea[now],y=eb[now];
if(t[x]==0||t[x]==-1) {
int pre=t[x];
Confirm(x,0);
solve(now+1);
Confirm(x,pre);
}
if((t[x]==1||t[x]==-1)&&(t[y]==0||t[y]==-1)) {
int prex=t[x],prey=t[y];
Confirm(x,1),Confirm(y,0);
solve(now+1);
Confirm(x,prex),Confirm(y,prey);
}
}
int f[N][2];
void DP(int v,int fr) {
f[v][0]=f[v][1]=1;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(to==fr) continue ;
DP(to,v);
f[v][0]=f[v][0]*(f[to][0]+f[to][1])%mod;
f[v][1]=f[v][1]*f[to][0]%mod;
}
}
int main() {
memset(t,-1,sizeof(t));
n=Get(),m=Get();
int a,b;
for(int i=1;i<=n;i++) FA[i]=i;
for(int i=1;i<=m;i++) {
a=Get(),b=Get();
if(Getf(a)==Getf(b)) {
e[++tot]=(edge) {a,b};
ea.push_back(a);
eb.push_back(b);
st.push_back(a);
st.push_back(b);
E[a].push_back(b);
E[b].push_back(a);
} else {
add(a,b),add(b,a);
FA[Getf(a)]=Getf(b);
}
}
sort(st.begin(),st.end());
int cc=unique(st.begin(),st.end())-st.begin();
while(st.size()>cc) st.pop_back();
build(1,1,n);
dfs(1);
dfs2(1,1);
solve(0);
cout<<ans;
return 0;
}