暴力枚举非树边取值做DP可得75。
注意到每次枚举出一个容斥状态的时候，都要做大量重复操作。
建立虚树，预处理出虚树上两点间的转移系数。也可动态DP解决。
树上倍增、动态DP、虚树DP似乎是这种问题的三种通用解法。
代码不是特别长但极其难写，预处理过程中要考虑各种情况。水平不够只好抄代码。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 5 using namespace std; 6 7 const int N=100010,mod=998244353; 8 bool mark[N],vis[N],ban[N][2]; 9 int n,m,u,v,tot,tim,ans,sz[N],du[N],dv[N],dfn[N],dp[N][2],g[N][2]; 10 struct P{ int k0,k1; }K[N][2]; 11 12 P operator +(const P &a,const P &b){ return (P){(a.k0+b.k0)%mod,(a.k1+b.k1)%mod}; } 13 P operator *(const P &a,int x){ return (P){int(1ll*a.k0*x%mod),int(1ll*a.k1*x%mod)}; } 14 15 struct Edge{ 16 int cnt,h[N],to[N<<1],nxt[N<<1]; 17 P val[100][2]; 18 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 19 void add(int u,int v,const P &a,const P &b){ 20 to[++cnt]=v; val[cnt][0]=a; val[cnt][1]=b; nxt[cnt]=h[u]; h[u]=cnt; 21 } 22 23 void dfs1(int x,int fa){ 24 dfn[x]=++tim; 25 For(i,x) if ((k=to[i])!=fa){ 26 if (!dfn[k]) dfs1(k,x),sz[x]+=sz[k]; 27 else if (dfn[k]<dfn[x]) du[++tot]=x,dv[tot]=k,mark[x]=mark[k]=1; 28 } 29 mark[x]|=(sz[x]>=2); if (mark[x]) sz[x]=1; 30 } 31 32 void dfs3(int x){ 33 dp[x][0]=ban[x][0] ? 0 : g[x][0]; 34 dp[x][1]=ban[x][1] ? 0 : g[x][1]; 35 For(i,x){ 36 dfs3(k=to[i]); 37 dp[x][0]=1ll*dp[x][0]*(1ll*val[i][0].k0*dp[k][0]%mod+1ll*val[i][0].k1*dp[k][1]%mod)%mod; 38 dp[x][1]=1ll*dp[x][1]*(1ll*val[i][1].k0*dp[k][0]%mod+1ll*val[i][1].k1*dp[k][1]%mod)%mod; 39 } 40 } 41 }G1,G2; 42 43 int dfs2(int x){ 44 g[x][0]=g[x][1]=1; vis[x]=1; int t=0; 45 for (int i=G1.h[x],k; i; i=G1.nxt[i]) if (!vis[k=G1.to[i]]){ 46 int z=dfs2(k); 47 if (!z) g[x][0]=1ll*g[x][0]*(g[k][0]+g[k][1])%mod,g[x][1]=1ll*g[x][1]*g[k][0]%mod; 48 else{ 49 if (mark[x]) G2.add(x,z,K[k][0]+K[k][1],K[k][0]); 50 else K[x][0]=K[k][0]+K[k][1],K[x][1]=K[k][0],t=z; 51 } 52 } 53 if (mark[x]) K[x][0]=(P){1,0},K[x][1]=(P){0,1},t=x; 54 else K[x][0]=K[x][0]*g[x][0],K[x][1]=K[x][1]*g[x][1]; 55 return t; 56 } 57 58 int main(){ 59 freopen("bzoj5287.in","r",stdin); 60 freopen("bzoj5287.out","w",stdout); 61 scanf("%d%d",&n,&m); 62 rep(i,1,m) scanf("%d%d",&u,&v),G1.add(u,v),G1.add(v,u); 63 G1.dfs1(1,0); mark[1]=1; dfs2(1); 64 for (int S=0; S<(1<<tot); S++){ 65 rep(i,1,tot) if (S&(1<<(i-1))) ban[dv[i]][0]=1,ban[du[i]][1]=1; else ban[dv[i]][1]=1; 66 G2.dfs3(1); ans=(ans+(dp[1][1]+dp[1][0])%mod)%mod; 67 rep(i,1,tot) if (S&(1<<(i-1))) ban[dv[i]][0]=0,ban[du[i]][1]=0; else ban[dv[i]][1]=0; 68 } 69 printf("%d\n",ans); 70 return 0; 71 }