bzoj4784 [Zjoi2017]仙人掌

2023-07-25 15:21:34

Description

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在九条可怜手上有一张无自环无重边的无向连通图，但是她觉得这张图中的边数太少了，所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。经过权衡，她想要加边后得到的图为一棵仙人掌。不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

Input

多组数据，第一行输入一个整数T表示数据组数。

每组数据第一行输入两个整数n,m，表示图中的点数与边数。

接下来m行，每行两个整数u,v(1≤u,v≤n,u!=v)表示图中的一条边。保证输入的图联通且没有自环与重边

Sigma(n)<=5*10^5,m<=10^6,1<=m<=n*(n-1)/2

Output

对于每组数据，输出一个整数表示方案数，当然方案数可能很大，请对998244353取模后输出。

Sample Input

2
3 2
1 2
1 3
5 4
1 2
2 3
2 4
1 5

Sample Output

2
8
对于第一组样例合法加边的方案有 {}, {(2,3)}，共 2 种。

正解：仙人掌$DP$

这题好难啊。。我看题解都看了好久才看懂。。

先给两个博客：http://blog.csdn.net/akak__ii/article/details/65935711

ljh2000：http://www.cnblogs.com/ljh2000-jump/p/6613829.html

首先特判不是仙人掌的情况，只要判每个点到达根的路径是否大于$2$条就行了。

然后我们可以先把环拆掉，也就是把环边和对应的那个点与它父亲断开，因为环是不会对答案造成贡献的。然后这个仙人掌就会变成一个森林。于是我们就成功地把仙人掌$DP$变成了树形$DP$。我们单独考虑每棵树的答案，乘法原理一下就好。

然后就是对于每棵树统计答案了。

对于一个点$x$，我们设$f[x]$表示$x$这棵子树连边形成仙人掌的方案数。我们发现，可以分为两种情况：

1，$x$这棵子树一定不与祖先连边，这个是根的情况。

2，$x$这棵子树可能与祖先连边，这个是除了根以外其他点的情况。

对于第1种情况，我们把$x$所有的儿子$f[v]$都乘起来，并且我们计算一下$x$的儿子互相连边的情况，再乘起来就行了。

对于$x$的儿子互相连边的情况，我们可以找到一个规律。我们设$g[i]$表示$i$个儿子互相连边的合法方案数，那么$g[i]=g[i-1]+(i-1)*g[i-2]$。

这是怎么来的呢？我们考虑一下，如果第$i$个点不与其他点连边，那么方案数就是$g[i-1]$，否则，第$i$个点与第$j$个点连边，那么第$j$个点肯定不能与其他点连边，所以方案数是$g[i-2]$，总共有$i-1$种情况，所以$g[i]=g[i-1]+(i-1)*g[i-2]$。那么我们设$x$有$tot$个儿子，于是$f[x]=\prod f[v]*g[tot]$。

那么现在我们只要考虑第二种情况了。其实仔细想想，就是$x$的所有儿子$f[v]$相乘，再乘上$g[tot+1]$就行了。因为这就是$tot+1$个点互相连边的情况。于是$f[x]=\prod f[v]*g[tot+1]$。

于是这道题我们就完美地解决了。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <complex>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define rhl (998244353)

 #define inf (1<<30)

 #define M (1000010)

 #define N (500010)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 struct edge{ int nt,to; }G[*M];

 struct node{ int i,d; }a[N];

 int head[N],fa[N],dfn[N],dep[N],lu[N],n,m,cnt;

 ll f[N],g[N],ans;

 il int gi(){

     RG int x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void insert(RG int from,RG int to){

     G[++cnt]=(edge){head[from],to},head[from]=cnt; return;

 }

 il int cmpd(const node &a,const node &b){ return a.d<b.d; }

 il void pre(){ //预处理g数组

     g[]=g[]=;

     for (RG int i=;i<=;++i) g[i]=(g[i-]+(i-)*g[i-])%rhl;

     return;

 }

 il void dfs(RG int x,RG int p){

     fa[x]=p,dfn[x]=++cnt,dep[x]=dep[p]+;

     for (RG int i=head[x],v;i;i=G[i].nt){

     v=G[i].to; if (dfn[v]) continue;

     dfs(v,x);

     }

     return;

 }

 il void dp(RG int x,RG int rt){

     lu[x]=-,f[x]=; RG int tot=,v;

     for (RG int i=head[x];i;i=G[i].nt){

     v=G[i].to; if (v==fa[x] || lu[v]!=) continue;

     tot++; dp(v,); f[x]=f[x]*f[v]%rhl;

     }

     if (!rt) f[x]=f[x]*g[tot+]%rhl;

     else f[x]=f[x]*g[tot]%rhl;

     return;

 }

 il void work(){

     n=gi(),m=gi(),cnt=;

     for (RG int i=;i<=n;++i) lu[i]=fa[i]=dep[i]=dfn[i]=head[i]=;

     for (RG int i=,u,v;i<=m;++i) u=gi(),v=gi(),insert(u,v),insert(v,u);

     cnt=; dfs(,);

     for (RG int i=,u,v;i<=m;++i){ //统计每个点到根的路径数

     u=G[i<<].to,v=G[i<<|].to;

     if (dfn[u]<dfn[v]) swap(u,v);

     while (u!=v){

         if (lu[u]==){ printf("0\n"); return; }

         lu[u]++,u=fa[u];

     }

     }

     for (RG int i=;i<=n;++i) a[i].i=i,a[i].d=dep[i];

     sort(a+,a+n+,cmpd); ans=;

     for (RG int i=,x;i<=n;++i){

     x=a[i].i; if (lu[x]==-) continue;

     dp(x,); ans=ans*f[x]%rhl;

     }

     printf("%lld\n",ans); return;

 }

 int main(){

     File("cactus");

     pre(); RG int T=gi();

     while (T--) work();

     return ;

 }

码农公寓

Description

Input

Output

Sample Input

Sample Output

相关文章