题面

有一张\(n\)点\(m\)边的、不一定联通的无向图。

如果选了一条边，就不能选其两个端点。

现在同时选点和边，那么最多能够选的点边数量和为多少。

同时，回答使点边数最大的方案数。

• \(n\leq10^5,m\leq3*10^5\)

  解析

  设答案为\(ans\),方案数为\(tot\)。

  讨论一下联通块的形态：

• \(m=n-1\)：\(ans=n,tot=1\)
• \(m=n\)：\(ans=m\)，环中\(tot=2\)，树的部分\(tot\)值可以通过\(dp\)求出

• \(m>n\)：\(ans=m\)，强连通分量\(tot=1\)，树的部分\(tot\)值可以通过\(dp\)求出

树的部分的\(dp\)：

设\(dp[i][0/1]\)表示统计到\(i\)号点，选不选该点的方案数。

然后从儿子转移，讨论一下就行。

综上，其实把强联通分量缩点后直接树形\(DP\)就行了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define re register#define il inline#define fp(i,a,b) for(re int i=a;i<=b;++i)#define fq(i,a,b) for(re int i=a;i>=b;--i)using namespace std;const int N=5e5+100,mod=998244353;int n,m,h[N],cnt=1,ans,dfn[N],low[N],sta[N],top,tot,sz[N],bl[N],scc,Esz[N],f[2][N],g[2][N];bool vis[N];struct dat{int u,v;}a[N<<1];struct Edge{int to,nxt;}e[N<<1];il void add(re int u,re int v){ e[++cnt]=(Edge){v,h[u]};h[u]=cnt; e[++cnt]=(Edge){u,h[v]};h[v]=cnt;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void Tarjan(re int u,re int las){ dfn[u]=low[u]=++tot;sta[++top]=u;vis[u]=1; re int v; for(re int i=h[u];i+1;i=e[i].nxt) if((i^1)^las) { re int v=e[i].to; if(!dfn[v]) Tarjan(v,i),low[u]=min(low[u],low[v]); else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ++scc; do{v=sta[top--];vis[v]=0;++sz[scc];bl[v]=scc;}while(u^v); }}il void dfs(re int u){ f[0][u]=sz[u];f[1][u]=Esz[u];g[0][u]=g[1][u]=1;vis[u]=1; for(re int i=h[u];i+1;i=e[i].nxt) { re int v=e[i].to; if(vis[v]) continue; dfs(v); if(f[0][v]>f[1][v]) f[0][u]+=f[0][v],g[0][u]=1ll*g[0][u]*g[0][v]%mod; if(f[0][v]==f[1][v]) f[0][u]+=f[0][v],g[0][u]=1ll*g[0][u]*(g[0][v]+g[1][v])%mod; if(f[0][v]
          
           f[1][v]+1) f[1][u]+=f[0][v],g[1][u]=1ll*g[1][u]*g[0][v]%mod; if(f[0][v]==f[1][v]+1) f[1][u]+=f[0][v],g[1][u]=1ll*g[1][u]*(g[0][v]+g[1][v])%mod; if(f[0][v]
           
            f[1][i]) ans+=f[0][i],tot=1ll*tot*g[0][i]%mod; } printf("%d\n%d\n",ans,tot); return 0;}