题目描述
从前有一名毒瘤。
毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（例如给一个区间内的数同时加上 $c$，或者将一个区间内的数同时开平方根），并且支持询问区间的和。毒瘤考虑了 $n$ 个这样的修改操作,并将它们编号为 $1 ldots n$。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。
当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作之间的关系：有 $m$ 对「互相排斥」的修改操作，第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题中同时含有 $u_i$ 和 $v_i$ 这两个操作时，这道题就会变得不可做。另一方面，当一道题中不包含任何「互相排斥」的操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：$m − n$ 是一个很小的数字（参见「数据范围」中的说明），且任意两个修改操作都是连通的。两个修改操作 $a, b$ 是连通的，当且仅当存在若干操作 $t_0, t_1, ... , t_l$，使得 $t_0 = a,t_l = b$，且对任意 $1 le i le l$，$t_{i−1}$ 和 $t_i$ 都是「互相排斥」的修改操作。
一对「互相排斥」的修改操作称为互斥对。现在毒瘤想知道，给定值 $n$ 和 $m$ 个互斥对，他一共能出出多少道可做的不同的数据结构题。两个数据结构题是不同的，当且仅当其中某个操作出现在了其中一个题中，但是没有出现在另一个题中。
题解
为什么看到的题解都是虚树啊？这里介绍一个 $ ext{ddp}$ 做法。
如果 $m=n-1$ 的话，那就是简单 $ ext{dp}$ ： $f[u][0/1]$ 表示 $u$ 这个点选/不选的方案数，转移显然。
那现在如果 $n le m$ 的话，由于 $m-n+1$ 不大所以我们只要减掉不合法情况即可，容易想到容斥。即枚举状态然后把状态中为 $1$ 的边的两端强制选（即 $f[u][0]=0$ ），然后再做 $ ext{dp}$ 即可，可是这样是 $O(2^{m-n+1}n)$ 的过不去。然后我们发现转移可以写成矩阵的形式，于是就可以用树剖+线段树维护矩阵乘即可，效率 $O(2^{m-n+1}log^2n+n)$ 。
代码
#include <bits/stdc++.h> using namespace std; const int N=1e5+15,M=N<<1,P=998244353; int n,m,hd[N],V[M],nx[M],t=1,top[N],sz[N],dp[N],fa[N]; int son[N],f[N][2],h[N],df[N],id[N],b[15],g[N][2],s; vector<int>G[N][2];bool vis[N]; struct O{int p[2][2];}W,a[N<<2]; int X(int x){return x>=P?x-P:x;} int K(int x,int y){ int z=1; for (;y;y>>=1,x=1ll*x*x%P) if (y&1) z=1ll*z*x%P; return z; } O Mul(O A,O B){ for (int i=0;i<2;i++) for (int j=0;j<2;j++){ W.p[i][j]=0; for (int k=0;k<2;k++) W.p[i][j]=X(W.p[i][j]+1ll*A.p[k][j]*B.p[i][k]%P); } return W; } void add(int u,int v){ nx[++t]=hd[u];V[hd[u]=t]=v; } void dfs(int u,int fr){ dp[u]=dp[fa[u]=fr]+1;sz[u]=1;vis[u]=1; for (int v,i=hd[u];i;i=nx[i]){ if (vis[v=V[i]]) continue; dfs(v,u);sz[u]+=sz[v]; if (sz[v]>sz[son[u]]) son[u]=v; } } void Dfs(int u,int tp){ top[u]=tp;h[u]=df[id[u]=++t]=u; if (son[u]) Dfs(son[u],tp),h[u]=h[son[u]]; for (int i=hd[u];i;i=nx[i]) if (V[i]!=son[u] && fa[V[i]]==u) Dfs(V[i],V[i]); } void Dp(int u){ f[u][0]=f[u][1]=g[u][0]=g[u][1]=1; for (int v,i=hd[u];i;i=nx[i]) if (fa[v=V[i]]==u) Dp(v), f[u][0]=1ll*f[u][0]*(f[v][0]+f[v][1])%P, f[u][1]=1ll*f[u][1]*f[v][0]%P; } #define Ls k<<1 #define Rs k<<1|1 #define mid ((l+r)>>1) void build(int k,int l,int r){ if (l==r){ int u=df[l]; for (int i=hd[u];i;i=nx[i]) if (V[i]!=son[u] && fa[V[i]]==u) g[u][0]=1ll*g[u][0]*(f[V[i]][0]+f[V[i]][1])%P, g[u][1]=1ll*g[u][1]*f[V[i]][0]%P; a[k]=(O){g[u][0],g[u][0],g[u][1],0};return; } build(Ls,l,mid);build(Rs,mid+1,r); a[k]=Mul(a[Rs],a[Ls]); } O qry(int k,int l,int r,int L,int R){ if (L<=l && r<=R) return a[k]; if (mid<L) return qry(Rs,mid+1,r,L,R); if (mid>=R) return qry(Ls,l,mid,L,R); return Mul(qry(Rs,mid+1,r,L,R),qry(Ls,l,mid,L,R)); } void upd(int k,int l,int r,int x,int v0,int v1){ if (l==r){a[k]=(O){v0,v0,v1,0};return;} if (mid>=x) upd(Ls,l,mid,x,v0,v1); else upd(Rs,mid+1,r,x,v0,v1); a[k]=Mul(a[Rs],a[Ls]); } void del(int x,int o){ O v;int v0,v1,u; while(x!=1){ v=qry(1,1,n,id[x],id[h[x]]); v0=v.p[0][0],v1=v.p[1][0],u=fa[x]; if (!o) G[u][0].push_back(g[u][0]),G[u][1].push_back(g[u][1]); g[u][0]=1ll*g[u][0]*K(X(v0+v1),P-2)%P; g[u][1]=1ll*g[u][1]*K(v0,P-2)%P;x=top[u]; } } void ins(int x,int o){ O v;int v0,v1,u; while(x!=1){ v=qry(1,1,n,id[x],id[h[x]]); v0=v.p[0][0],v1=v.p[1][0],u=fa[x]; if (o){ int z=G[u][0].size(); g[u][0]=G[u][0][z-1];G[u][0].pop_back(); g[u][1]=G[u][1][z-1];G[u][1].pop_back(); } else g[u][0]=1ll*g[u][0]*(v0+v1)%P, g[u][1]=1ll*g[u][1]*v0%P; upd(1,1,n,id[u],g[u][0],g[u][1]); x=top[u]; } } int main(){ cin>>n>>m; for (int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v), add(u,v),add(v,u); t=0;dfs(1,0);Dfs(1,1); Dp(1);build(1,1,n);t=0; for (int u,v,i=1;i<=m;i++){ u=V[i<<1],v=V[i<<1|1]; if (dp[u]>dp[v]) swap(u,v); if (fa[v]!=u) b[t++]=i; } for (int F,i=(1<<t)-1;~i;i--){ F=1; for (int j=0;j<t;j++) if ((i>>j)&1){ F=P-F; for (int u,k=0;k<2;k++){ u=V[b[j]<<1|k];del(top[u],0); G[u][0].push_back(g[u][0]); G[u][1].push_back(g[u][1]); upd(1,1,n,id[u],g[u][0]=0,g[u][1]); ins(top[u],0); } } O v=qry(1,1,n,1,id[h[1]]); s=X(1ll*F*(v.p[0][0]+v.p[1][0])%P+s); for (int z,j=t-1;~j;j--) if ((i>>j)&1){ F=P-F; for (int u,k=0;k<2;k++){ u=V[b[j]<<1|k];del(top[u],1); z=G[u][0].size(); g[u][0]=G[u][0][z-1];G[u][0].pop_back(); g[u][1]=G[u][1][z-1];G[u][1].pop_back(); upd(1,1,n,id[u],g[u][0],g[u][1]); ins(top[u],1); } } } cout<<s<<endl;return 0; }