显然的做法是暴力枚举非树边所连接两点的选或不选，大力dp。考场上写的是最暴力的O(3n-mn)，成功比大众分少10分。容斥或者注意到某些枚举是不必要的就能让底数变成2。但暴力的极限也就到此为止。
每次重新dp做了大量重复的事，考虑从减少重复计算方面优化。先跑一遍没有限制的树形dp。将非树边所连接的点拎出来建一棵虚树。注意到虚树中某点对其父亲的贡献系数（也即由该点到其父亲的链上点的dp值与其关系）是不变的，那么dp出系数，依旧暴力枚举非树边就可以了。一定程度上与noip2018d2t3有相似之处？
码起来非常长（虽然似乎并没有很难写），可能是我姿势不对。注意暴力枚举非树边时不应标记其是否强制被选，而是标记强制被选的次数，防止回溯时出问题。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100050 #define P 998244353 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,p[N],f[N][2],id[N][2],dfn[N],size[N],fa[N][19],deep[N],num[N][2][2],tmp[2][2],tot,cnt,t,u,ans=0; bool vis[N],flag[N]; struct data{int to,nxt; }edge[N<<1]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} int ksm(int a,int k) { int s=1; for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P; return s; } int inv(int a){return ksm(a,P-2);} void dfs(int k) { vis[k]=1;f[k][0]=f[k][1]=1;dfn[k]=++tot;size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k][0]) if (vis[edge[i].to]) { flag[k]=flag[edge[i].to]=1;bool tag=1; for (int j=1;j<=cnt;j++) if (id[j][0]==edge[i].to&&id[j][1]==k) {tag=0;break;} if (tag) cnt++,id[cnt][0]=k,id[cnt][1]=edge[i].to; } else { fa[edge[i].to][0]=k; deep[edge[i].to]=deep[k]+1; dfs(edge[i].to); f[k][0]=1ll*f[k][0]*(f[edge[i].to][0]+f[edge[i].to][1])%P, f[k][1]=1ll*f[k][1]*f[edge[i].to][0]%P; size[k]+=size[edge[i].to]; } } int lca(int x,int y) { if (deep[x]<deep[y]) swap(x,y); for (int j=18;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j]; if (x==y) return x; for (int j=18;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0]; } namespace virtual_tree { int m,p[N],t,g[N][2],point[N],stk[N],top,cho[N]; struct data{int to,nxt;}edge[N<<1]; void addedge(int x,int y){t++;flag[x]=flag[y]=1;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} bool cmp(const int&a,const int&b){return dfn[a]<dfn[b];} void build() { for (int i=1;i<=n;i++) if (flag[i]) point[++m]=i; sort(point+1,point+m+1,cmp); stk[top=1]=1; for (int i=(point[1]==1)+1;i<=m;i++) { int x=lca(point[i],stk[top]); if (x==stk[top]) stk[++top]=point[i]; else { while (top>1&&deep[stk[top-1]]>=deep[x]) addedge(stk[top-1],stk[top]),top--; if (stk[top]!=x) addedge(x,stk[top--]),stk[++top]=x; stk[++top]=point[i]; } } while (top>1) addedge(stk[top-1],stk[top]),top--; } void copy(int k) { g[k][0]=f[k][0],g[k][1]=f[k][1]; for (int i=p[k];i;i=edge[i].nxt) { copy(edge[i].to); g[k][0]=1ll*g[k][0]*inv((1ll*num[edge[i].to][0][0]*f[edge[i].to][0]+1ll*num[edge[i].to][0][1]*f[edge[i].to][1])%P)%P; g[k][1]=1ll*g[k][1]*inv((1ll*num[edge[i].to][1][0]*f[edge[i].to][0]+1ll*num[edge[i].to][1][1]*f[edge[i].to][1])%P)%P; } } void dp(int k) { if (cho[k]) g[k][0]=0; for (int i=p[k];i;i=edge[i].nxt) { dp(edge[i].to); g[k][0]=1ll*g[k][0]*((1ll*num[edge[i].to][0][0]*g[edge[i].to][0]+1ll*num[edge[i].to][0][1]*g[edge[i].to][1])%P)%P; g[k][1]=1ll*g[k][1]*((1ll*num[edge[i].to][1][0]*g[edge[i].to][0]+1ll*num[edge[i].to][1][1]*g[edge[i].to][1])%P)%P; } } int getans() { copy(1); dp(1); return (g[1][0]+g[1][1])%P; } void dfs(int k,int s) { if (k>cnt) {ans=((ans+s*getans())%P+P)%P;return;} cho[id[k][0]]++,cho[id[k][1]]++;dfs(k+1,-s); cho[id[k][0]]--,cho[id[k][1]]--;dfs(k+1,s); } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5287.in","r",stdin); freopen("bzoj5287.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(); addedge(x,y),addedge(y,x); } fa[1][0]=1;deep[1]=1;dfs(1); for (int j=1;j<19;j++) for (int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; virtual_tree::build(); for (int i=1;i<=n;i++) if (flag[i]) virtual_tree::point[++u]=i; for (int j=1;j<=u;j++) { int i=virtual_tree::point[j]; num[i][0][0]=num[i][1][1]=1; if (i!=1) { int x=fa[i][0],y=i; do { tmp[0][0]=(num[i][0][0]+num[i][1][0])%P,tmp[0][1]=(num[i][0][1]+num[i][1][1])%P, tmp[1][0]=num[i][0][0],tmp[1][1]=num[i][0][1]; num[i][0][0]=tmp[0][0],num[i][0][1]=tmp[0][1],num[i][1][0]=tmp[1][0],num[i][1][1]=tmp[1][1]; if (!flag[x]) for (int k=p[x];k;k=edge[k].nxt) if (edge[k].to!=y&&edge[k].to!=fa[x][0]) { num[i][0][0]=1ll*num[i][0][0]*(f[edge[k].to][1]+f[edge[k].to][0])%P; num[i][0][1]=1ll*num[i][0][1]*(f[edge[k].to][1]+f[edge[k].to][0])%P; num[i][1][0]=1ll*num[i][1][0]*f[edge[k].to][0]%P; num[i][1][1]=1ll*num[i][1][1]*f[edge[k].to][0]%P; } y=x,x=fa[x][0]; }while(!flag[y]); } } virtual_tree::dfs(1,1); cout<<ans; return 0; }