【题解】ZJOI2017仙人掌

　　感觉这题很厉害啊，虽然想了一天多但还是失败了……(；д；)

　　这题首先注意到给定图中如果存在环其实对于答案是没有影响的。然后关键之处就在于两个 \(dp\) 数组，其中 \(f[u]\) 表示以 \(u\) 为根的子树中能构成仙人掌的方案数，而 \( g[x] \) 则表示 \(x\) 个节点之间两两相互搭配（可以不搭配）的总方案数。转移则为：

　\(f[u] = \prod f[v] * g[tot + [u != root]]\)

　　其中 \(v\) 为 \(u\) 的儿子节点，而 \(tot\) 表示 \(u\) 的总儿子个数。为什么这样做是对的呢？我也感到非常的困惑。之前自己在思考的时候其实有一个问题一直难住我：一个节点的儿子之间可以相互连边，这怎样处理？但此时我们将这些方案巧妙地连接在了一起。我们可以默认为求出来的 \(f[u]\) 中的方案数均为有一条边连向外界的方案。当这个方案匹配到另一子树的一种方案上的时候，表示这两条连向外界的边连接在了一起。若有没有匹配的，说明这条边没有连出去或连向根节点（若连向根节点且该点为儿子节点则说明没有连出去），但一样是合法的。

　　非常的厉害啊~其实感觉自己现在各种知识储备都还算可以了，但就是不够大胆，不能勇敢的提出一些想法和设想。一定要努力放开自己的思维，先猜测，再证明~

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000000

#define mod 998244353

#define int long long

int n, m, dep[maxn], g[maxn];

int timer, dfn[maxn], f[maxn];

int fa[maxn], mark[maxn], tot;

int cnt, ans;

struct edge

{

    int cnp, head[maxn], to[maxn], last[maxn];

    edge() { cnp = ; }

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;

struct node

{

    int id, dep;

}a[maxn];

bool cmp(node a, node b) { return a.dep < b.dep; }

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

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

    return x * k;

}

void pre()

{

    g[] = g[] = ;

    for(int i = ; i < maxn; ++ i) g[i] = (g[i - ] + (i - )*g[i - ]) % mod;

    return;

}

void Tarjan(int u)

{

    dfn[u] = ++ timer;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

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

        fa[v] = u; dep[v] = dep[u] + ; Tarjan(v);

    }

    return;

}

void dfs(int u, int rt)

{

    mark[u] = -; f[u] = ; int tot = ;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i]; if(v == fa[u] || mark[v] != ) continue;

        tot ++; dfs(v, ); f[u] = f[u] * f[v] % mod;

    }

    if(!rt) f[u] = f[u] * g[tot + ] % mod;

    else f[u] = f[u] * g[tot] % mod;

    return;

}

void Work()

{

    n = read(), m = read(); E1.cnp = ;

    for(int i = ; i <= n; i ++) mark[i] = fa[i] = dep[i] = dfn[i] = E1.head[i] = ;

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

    {

        int u = read(), v = read();

        E1.add(u, v);

    }

    dep[] = ; Tarjan();

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

    {

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

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

        while(u != v)

        {

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

            mark[u] ++; u = fa[u];

        }

    }

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

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

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

    {

        int x = a[i].id; if(mark[x] == -) continue;

        dfs(x, ); ans = ans * f[x] % mod;

    }

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

}

signed main()

{

    pre(); int T = read();

    while(T --) Work();

    return ;

}

巴特西

【题解】ZJOI2017仙人掌

最新文章

热门文章