uoj#290. 【ZJOI2017】仙人掌（数数+仙人掌+树形dp）

传送门

这图可以说是非常形象了2333

模拟赛的时候打了个表发现为一条链的时候答案是$2^{n-2}$竟然顺便过了第一个点

然后之后订正的时候强联通分量打错了调了一个上午

首先不难发现我们可以去掉所有在环上的边，那么就变成了一个森林，不同的树之间不可能有连边，那么只要所有树的答案乘起来就好了，只要在每一棵树内部树形$dp$即可

考虑对于$u$，它的子树如何统计答案

我们强制子树必须得向外连一条边（显然最多只有一条），然后往上统计

如果子树里没有向外连边，每一棵子树的答案乘起来

如果向外连边的话，那么要把子树内的边两两匹配上。设$g_i$为$i$个点互相两两匹配的方案数，那么递推式为$$g_i=g_{i-1}+(i-1)\times g_{i-2}$$

边界条件为$g_0=g_1=1$

上面的意思是，如果第$i$个不连边，那么方案数就是$g_{i-1}$，如果连边，那么有$i-1$种连法，连完后这两个点都不能再连边了

那么要把子树内的边两两匹配，如果当前节点是根，那么就是子树内向外连的每条链互相匹配，记$tot$为当前节点儿子个数，那么就是$g_{tot}$，否则链还可以继续往上连，那么是$g_{tot+1}$，可以考虑为把当前节点也加入匹配的队列，如果有链和它连上就代表这条链要继续向外连

然后记得开始的时候判一下是不是仙人掌就好了

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

inline void swap(R int &x,R int &y){x^=y^=x^=y;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

void write(int x){if(x>9)write(x/10);putchar(x%10+48);}

void writeln(R int x){write(x);putchar('\n');}

const int N=1e6+5,P=998244353;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

    R int res=1;

    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);

    return res;

}

struct eg{int v,nx,w;}e[N<<1];int head[N],tot=1;

inline void add_edge(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

int dfn[N],col[N],vis[N],f[N],g[N],st[N],low[N];

int n,m,cnt,top,tim,u,v,ans;bool qwq;

inline void clr(){fp(i,1,n)dfn[i]=col[i]=f[i]=vis[i]=head[i]=0;tim=cnt=top=qwq=0,tot=ans=1;}

void tarjan(int u,int fa){

    bool flag=0;st[++top]=u;

    dfn[u]=low[u]=++tim;

    go(u)if(v!=fa){

        if(!dfn[v]){

            tarjan(v,u);cmin(low[u],low[v]);

            if(low[v]<dfn[u]){

                if(flag)return qwq=1,void();

                flag=1;

            }

        }else{

            cmin(low[u],dfn[v]);

            if(low[v]<dfn[u]){

                if(flag)return qwq=1,void();

                flag=1;

            }

        }

    }

    if(low[u]==dfn[u])do{col[st[top--]]=u;}while(st[top+1]!=u);

}

void dp(int u,int fa){

    vis[u]=f[u]=1;int tot=0;

    go(u)if(v!=fa&&!e[i].w){

        dp(v,u),++tot;

        f[u]=mul(f[u],f[v]);

    }

    if(tot)f[u]=mul(f[u],fa?g[tot+1]:g[tot]);

}

int main(){

//	freopen("testdata.in","r",stdin);

    g[0]=g[1]=1;fp(i,2,N-5)g[i]=add(g[i-1],mul(i-1,g[i-2]));

    int T=read();

    while(T--){

        n=read(),m=read(),clr();

        fp(i,1,m)u=read(),v=read(),add_edge(u,v),add_edge(v,u);

        tarjan(1,0);

        if(qwq){writeln(0);continue;}

        fp(i,2,tot)e[i].w=(col[e[i].v]==col[e[i^1].v]);

        fp(i,1,n)if(!vis[i])dp(i,0),ans=mul(ans,f[i]);

        writeln(ans);

    }return 0;

}

巴特西

uoj#290. 【ZJOI2017】仙人掌（数数+仙人掌+树形dp）

最新文章

热门文章