首页 > 代码库 > bzoj4784 [Zjoi2017]仙人掌
bzoj4784 [Zjoi2017]仙人掌
Description
Input
Output
Sample Input
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]$。
于是这道题我们就完美地解决了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define rhl (998244353)15 #define inf (1<<30)16 #define M (1000010)17 #define N (500010)18 #define il inline19 #define RG register20 #define ll long long21 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)22 23 using namespace std;24 25 struct edge{ int nt,to; }G[2*M];26 struct node{ int i,d; }a[N];27 28 int head[N],fa[N],dfn[N],dep[N],lu[N],n,m,cnt;29 ll f[N],g[N],ans;30 31 il int gi(){32 RG int x=0,q=1; RG char ch=getchar();33 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();34 if (ch==‘-‘) q=-1,ch=getchar();35 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();36 return q*x;37 }38 39 il void insert(RG int from,RG int to){40 G[++cnt]=(edge){head[from],to},head[from]=cnt; return;41 }42 43 il int cmpd(const node &a,const node &b){ return a.d<b.d; }44 45 il void pre(){ //预处理g数组46 g[0]=g[1]=1;47 for (RG int i=2;i<=500000;++i) g[i]=(g[i-1]+(i-1)*g[i-2])%rhl;48 return;49 }50 51 il void dfs(RG int x,RG int p){52 fa[x]=p,dfn[x]=++cnt,dep[x]=dep[p]+1;53 for (RG int i=head[x],v;i;i=G[i].nt){54 v=G[i].to; if (dfn[v]) continue;55 dfs(v,x);56 }57 return;58 }59 60 il void dp(RG int x,RG int rt){61 lu[x]=-1,f[x]=1; RG int tot=0,v;62 for (RG int i=head[x];i;i=G[i].nt){63 v=G[i].to; if (v==fa[x] || lu[v]!=1) continue;64 tot++; dp(v,0); f[x]=f[x]*f[v]%rhl;65 }66 if (!rt) f[x]=f[x]*g[tot+1]%rhl;67 else f[x]=f[x]*g[tot]%rhl;68 return;69 }70 71 il void work(){72 n=gi(),m=gi(),cnt=1;73 for (RG int i=1;i<=n;++i) lu[i]=fa[i]=dep[i]=dfn[i]=head[i]=0;74 for (RG int i=1,u,v;i<=m;++i) u=gi(),v=gi(),insert(u,v),insert(v,u);75 cnt=0; dfs(1,0);76 for (RG int i=1,u,v;i<=m;++i){ //统计每个点到根的路径数77 u=G[i<<1].to,v=G[i<<1|1].to;78 if (dfn[u]<dfn[v]) swap(u,v);79 while (u!=v){80 if (lu[u]==2){ printf("0\n"); return; }81 lu[u]++,u=fa[u];82 }83 }84 for (RG int i=1;i<=n;++i) a[i].i=i,a[i].d=dep[i];85 sort(a+1,a+n+1,cmpd); ans=1;86 for (RG int i=1,x;i<=n;++i){87 x=a[i].i; if (lu[x]==-1) continue;88 dp(x,1); ans=ans*f[x]%rhl;89 }90 printf("%lld\n",ans); return;91 }92 93 int main(){94 File("cactus");95 pre(); RG int T=gi();96 while (T--) work();97 return 0;98 }
bzoj4784 [Zjoi2017]仙人掌