LOJ2250 [ZJOI2017] 仙人掌【树形DP】【DFS树】

题目分析：

不难注意到仙人掌边可以删掉。在森林中考虑树形DP。

题目中说边不能重复，但我们可以在结束后没覆盖的边覆盖一个重复边，不改变方案数。

接着将所有的边接到当前点，然后每两个方案可以任意拼接。然后考虑引一条边上去的情况，选一个点不与周围连边就行了。

判仙人掌利用dfs树与树前缀和即可。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int T,n,m,arr[maxn],C[maxn],d[maxn],up[maxn],dep[maxn];

 int f[maxn],gi[maxn];

 struct edge{int u,v,flag;}edges[maxn];

 vector <pair<int,int> > g[maxn];

 vector <int> nxt[maxn];

 void read(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         nxt[i].clear(),g[i].clear(),arr[i] = ,d[i]=,dep[i]=,up[i]=;

         f[i] = ;gi[i] = ;

     }

     for(int i=;i<=m;i++){

         scanf("%d%d",&edges[i].u,&edges[i].v);

         g[edges[i].u].push_back(make_pair(edges[i].v,i));

         g[edges[i].v].push_back(make_pair(edges[i].u,i));

         edges[i].flag = ;

     }

 }

 void DFST(int now,int dp){

     dep[now] = dp;

     for(auto it:g[now]){

         if(!dep[it.first]) {

             up[it.first] = it.second; nxt[now].push_back(it.first);

             DFST(it.first,dp+);

         }

         else if(dep[it.first] < dep[now]) continue;

         else d[it.first]++,d[now]--,edges[it.second].flag = ;

     }

 }

 void dfsup(int now){for(auto it:nxt[now]) dfsup(it),d[now] += d[it];}

 int cactus(){

     DFST(,); dfsup();

     for(int i=;i<=n;i++) if(d[i] > ) return ;

     for(int i=;i<=n;i++) if(d[i] == ) edges[up[i]].flag = ;

     return ;

 }

 void dfs(int now,int fa){

     arr[now] = ;int multi = ,cnt = ;

     for(auto it:nxt[now]){

         if(it == fa) continue;

         cnt++;dfs(it,now);

         multi = (1ll*multi*gi[it])%mod;

     }

     if(!cnt) f[now] = gi[now] = ;

     else{

         f[now] = (1ll*multi*C[cnt])%mod;

         gi[now] = f[now] + ((1ll*multi*C[cnt-])%mod)*cnt%mod;

         gi[now] %= mod;

     }

 }

 void work(){

     if(!cactus()) {puts("");return;}

     for(int i=;i<=n;i++) nxt[i].clear();

     for(int i=;i<=m;i++)

         if(!edges[i].flag){

             nxt[edges[i].u].push_back(edges[i].v);

             nxt[edges[i].v].push_back(edges[i].u);

         }

     int ans = ;

     for(int i=;i<=n;i++) if(!arr[i]) {dfs(i,); ans = (1ll*ans*f[i])%mod;}

     printf("%d\n",ans);

 }

 int main(){

     scanf("%d",&T);

     C[] = C[] = ;

     for(int i=;i<=;i++) C[i] = (C[i-] + (1ll*(i-)*C[i-])%mod)%mod;

     while(T--){

         read();

         work();

     }

     return ;

 }