题解：P4426 [HNOI/AHOI2018] 毒瘤

Claire0918 · 2025-09-11 20:45:40 · 题解

注意到 m - n 非常小，也就是该图是一棵树加上少量非树边。对于非树边 (u, v)，考虑 u 是否选择：若 u 选择则要求 v 不选，否则不限制 v，即可 \mathcal{O}(2^{m - n + 1}) 消除非树边限制。我们在树上设 f_{u, 0/1} 表示 u 选或不选时 u 子树内的方案数，就有

直接暴力 DP，时间复杂度 \mathcal{O}(n2^{m - n + 1}) \approx 2 \times 10^8，不能通过。

我们发现每次 DP 有意义的点很少。具体来说，我们对于所有连了非树边的点建虚树，那么对于虚树上一条边 (u, v)，其在原树上可能是链 u, x_1, x_2, \ldots, x_t, v，显然 x_i 都只有一个儿子 x_{i + 1} 的子树在虚树上（否则 x_i 一定在虚树上），我们记 x_i 除了 x_{i + 1} 外的儿子为 \{y_i\}，于是

中后面的积式是不变的，仅有前面一项与 x_{i + 1} 相关的在不同的 DP 中变化，即 f_{x_i} 仅随 f_{x_{i + 1}} 变化。归纳一下，f_u 仅随 f_v 变化，也就是说我们可以直接在虚树上 DP。

这样的变化显然是线性的，我们将那一积式的定值设为 p_{x_i, 0/1}，设

那么就有

从而

还有初始的

于是我们可以 DFS 建虚树，在建虚树时顺便转移 \{k_i\}，就可以直接在虚树上做 DP 了。时间复杂度降到 \mathcal{O}(n + (n - m + 1)2^{n - m + 1})，可以通过。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10, maxm = maxn + 10, mod = 998244353;

struct{
    struct{
        int v, nex;
        pair<int, int> w1, w2;
    } edge[maxm << 1];
    int head[maxn], top = 0;
    inline void add(int u, int v, pair<int, int> w1 = make_pair(0, 0), pair<int, int> w2 = make_pair(0, 0), bool o = true){
        edge[++top].v = v, edge[top].w1 = w1, edge[top].w2 = w2, edge[top].nex = head[u], head[u] = top, o && (add(v, u, w1, w2, false), 1538);
    }
} gr, vt;

int n, m, tot = 0, tota = 0, res = 0;
int dfn[maxn], p[maxn][2], subinvt[maxn], f[maxn][2];
bool invt[maxn], del[maxn][2];
pair<int, int> a[maxn], k[maxn][2];
int head[maxn], top = 0;

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

inline pair<int, int> operator + (const pair<int, int> & x, const pair<int, int> & y){
    return make_pair(mod_add(x.first, y.first), mod_add(x.second, y.second));
}

inline pair<int, int> operator * (const pair<int, int> & x, const int & y){
    return make_pair((long long)x.first * y % mod, (long long)x.second * y % mod);
}

inline void dfs1(int u, int fa){
    dfn[u] = ++tot;
    for (int i = gr.head[u]; i; i = gr.edge[i].nex){
        const int v = gr.edge[i].v;
        if (v != fa){
            if (!dfn[v]){
                dfs1(v, u), subinvt[u] += subinvt[v];
            }else{
                invt[u] = true;
                if (dfn[u] > dfn[v]){
                    a[++tota] = make_pair(u, v);
                }
            }
        }
    }
    invt[u] |= subinvt[u] >= 2, subinvt[u] = subinvt[u] || invt[u];
}

inline int dfs2(int u){
    dfn[u] = p[u][0] = p[u][1] = 1;
    int ret = 0;
    for (int i = gr.head[u]; i; i = gr.edge[i].nex){
        const int v = gr.edge[i].v;
        if (!dfn[v]){
            const int pos = dfs2(v);
            if (!pos){
                p[u][0] = (long long)p[u][0] * mod_add(p[v][0], p[v][1]) % mod, p[u][1] = (long long)p[u][1] * p[v][0] % mod;
            }else if (invt[u]){
                vt.add(u, pos, k[v][0] + k[v][1], k[v][0], false);
            }else{
                k[u][0] = k[v][0] + k[v][1], k[u][1] = k[v][0], ret = pos;
            }
        }
    }
    invt[u] ? ret = u, k[u][0] = make_pair(1, 0), k[u][1] = make_pair(0, 1) : (k[u][0] = k[u][0] * p[u][0], k[u][1] = k[u][1] * p[u][1]);
    return ret;
}

inline void dfs3(int u){
    f[u][0] = del[u][0] ? 0 : p[u][0], f[u][1] = del[u][1] ? 0 : p[u][1];
    for (int i = vt.head[u]; i; i = vt.edge[i].nex){
        const int v = vt.edge[i].v;
        const pair<int, int> w1 = vt.edge[i].w1, w2 = vt.edge[i].w2;
        dfs3(v), f[u][0] = (long long)f[u][0] * mod_add((long long)w1.first * f[v][0] % mod, (long long)w1.second * f[v][1] % mod) % mod;
        f[u][1] = (long long)f[u][1] * mod_add((long long)w2.first * f[v][0] % mod, (long long)w2.second * f[v][1] % mod) % mod;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++){
        int u, v;
        scanf("%d %d", &u, &v), gr.add(u, v);
    }
    dfs1(1, 0), mem(dfn, 0), invt[1] = true, dfs2(1);
    for (int sta = 0; sta < 1 << tota; sta++){
        for (int i = 1; i <= tota; i++){
            sta >> i - 1 & 1 ? del[a[i].first][0] = del[a[i].second][1] = true : del[a[i].first][1] = true;
        }
        dfs3(1), res = ((long long)res + f[1][0] + f[1][1]) % mod;
        for (int i = 1; i <= tota; i++){
            del[a[i].first][0] = del[a[i].first][1] = del[a[i].second][0] = del[a[i].second][1] = false;
        }
    }
    printf("%d", res);

return 0;
}