A simple Blog for wyx I've been down the bottle hoping.
ZJOI Day1 T1 仙人掌 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:58

考试的时候全程刚这题现在一看实在是有点亏啊…………

这题的仙人掌要求是没有重边的,那么我们可以在连完一种方案之后把剩下的没有被覆盖的边变成一个重边让他有覆盖

这样就变成了给定一棵树,找个方案使他的所有的边都被覆盖

树形dp即可

$f(x)$ 表示做完了 $x$ 的子树,没有路径向上扩展的方案数

$g(x)$ 表示做完了 $x$ 的子树,有路径可以向上扩展的方案数

$h(x)$ 表示 $x$ 个儿子互相连的方案数

对于 $h(x)$ 考虑他的第 $x$ 儿子的情况,如果他和之前的儿子相连,那么有 $x-1$ 种连法,子问题为 $f(x-2)$ , 否则的话和 $x-1$ 个儿子互相连的方案数相同

对于 $f(x)$ 每个儿子都必须可以往上扩展,而且每个儿子之间完全独立所以是 $\prod g_{son}$ ,然后假设儿子一共$num$ 个,那么一共有 $h(num)$ 的互相匹配的方案,乘起来才是所有的方案。

对于 $g(x)$ 首先 $x$ 可以自己向上扩展,方案数是 $f(x)$ ,或者我们可以选择一个儿子,他的方案数乘上除了他以外的所有儿子的方案数以及其他儿子互相连边的方案数就是选他的方案数,儿子的选择一共有 $num$ 种。

综上我们有

$$h(x) = h(x-1) + (x-1)\times h(x-2)$$

$$f(x) = h_{num}\prod g_{son} $$

$$g(x) = f(x) + num *h_{num-1}\times \prod g_{son}$$

记得要判断不是仙人掌的情况

人傻所以写了个$tarjan$

现在思考一下其实可以记录一下每个节点的父亲然后一路爬上去

还有一个转化是环啥用都没有可以直接拆开,但是要注意环上有的点还是有用的,开始的时候直接把环上的所有的点全都拆掉了结果GG了,不信的话你画一个两个环中间几个点就知道是怎么回事了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 5e5+5;
const int M = N << 1;
const int mod = 998244353;
typedef long long LL;
using namespace std;

bool is_cactus, vis[N+5];
LL F[N+5], H[N+5], G[N+5];
int col[N+5];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int head[N];

struct graph{
    int from, next, to;
    bool ban;
    graph () {}
    graph (int _from,int _next,int _to,bool _ban = true)
    :from(_from),next(_next),to(_to),ban(_ban){}
}edge[M];

int cnt = 1;

inline void add(int x,int y) {
    edge[++cnt] = graph(x,head[x],y,1); head[x] = cnt;
    edge[++cnt] = graph(y,head[y],x,1); head[y] = cnt;
}

int low[N], dfn[N], times;
int stack[N], top;

inline void DFS(int x, int fa) {
    dfn[x] = low[x] = ++times;
    stack[++top] = x;
    bool flag = false;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa)  {
            if(!dfn[edge[i].to]) {
                DFS(edge[i].to,x);
                low[x] = min(low[x],low[edge[i].to]);
                if(low[edge[i].to] < dfn[x]) {
                    if(flag) {
                        is_cactus = false;
                        return;
                    }
                    else flag = true;
                }
            }
            else {
                low[x] = min(low[x],dfn[edge[i].to]);
                if(low[edge[i].to] < dfn[x]) {
                    if(flag) {
                        is_cactus = false;
                        return;
                    }
                    else flag = true;
                }
            }
        }
    }
    if(low[x] == dfn[x])  {
        while(1) {
            col[stack[top--]] = x;
            if(stack[top+1] == x) break;
        }
    }
}

void DFS2(int x,int fa) {
//  cout << x << endl;
    vis[x] = 1, F[x] = 1, G[x] = 0;
    int cnt = 0;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].ban && edge[i].to != fa) {
            DFS2(edge[i].to,x);
            F[x] = F[x] * G[edge[i].to] % mod;
            cnt ++;
        }
    }
//cout << x << endl;
//  cout << x << " " << cnt << endl;
    if(cnt > 0)
        G[x] = (F[x] * H[cnt] + F[x] * H[cnt-1]  % mod * cnt)  % mod;
    else 
        G[x] = (F[x] * H[cnt])  % mod;
    F[x] = F[x] * H[cnt] % mod;
//  cout << F[x] << endl;
//  printf("f[%d] = %d, G[%d] = %d\n", x, F[x], x, G[x]);
}

inline void init(int x) {
    for(int i=1;i<=x;++i) head[i] = 0, col[i] = 0, dfn[i] = 0, low[i] = 0, vis[i] = false;
    cnt = 1; is_cactus = true; times = 0; top = 0;
}

int main() {
    //freopen("03.in","r",stdin);
    H[0] = H[1] = 1;
    for(int i=2;i<N;++i) H[i] = (H[i-1] + (i-1) * H[i-2]) % mod;
    int T; cin >> T;
    while(T--) {
        int n = read(), m = read();
        init(n);
        for(int i=1;i<=m;++i) add(read(),read());
        DFS(1,-1);
        if(!is_cactus) {
            puts("0");
            continue;
        }
        for(int i=2;i<=cnt;++i) if(col[edge[i].from] == col[edge[i].to]) edge[i].ban = false;
        LL ans = 1;
        for(int i=1;i<=n;++i) 
            if(!vis[i]) {
                DFS2(i,-1);
                ans = ans * F[i] % mod;
            }
        printf("%lld\n", ans);
    }
    return 0;
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP