P4426 [HNOI/AHOI2018] 毒瘤

· · 题解

非常好广义串并联图。虚树/no

根据经典结论，通过以下三个操作，最终得到的图的边数是 |V|=2k,|E|=3k 级别的，其中 k=m-n。

那么在这个题里面，可以发现 2^{2(m-n)} 枚举的复杂度是完全可以接受的，于是考虑直接去动态在上述三个过程中维护答案。

在哪里维护答案呢？比较显然的是在边上的情况。对于一条边 (u,v)，这条边可以代表着一个子图及这个子图的两个端点 u,v。那么对于一条边记录以下四个值：

对于“消串联”操作，我们发现可以直接枚举 u 是选还是不选，并对应加到 (v_1,v_2) 的四个权值中。

对于“消并联”操作，我们发现实际上两条边的对应权值相互独立，于是四个值对应相乘即可。

问题来到了“去断路”操作，我们发现没办法直接统计答案，坏诶。于是考虑去给每个点一个权值，缩一个断路就相当于把这个断路表示的子图的贡献挂在了这个结点上。于是每个结点就有两个权值：f_u,g_u 表示结点 u 选/不选，被缩在这个点子图的方案数贡献。

那么这个时候，“去断路“操作就可以手推一下，本质是将 u 的 f,g 通过断路的边转移到 v 的 f,g 上。

这里还要注意一点，此时的“消串联”操作也发生了变化，因为中间点选还是不选又乘上了一个该点自己的系数，稍微修改一下转移即可。

统计答案直接枚举哪些点选了，将点的对应权值与边的对应权值乘起来，再累加到答案即可。

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map

using namespace std;

typedef pair<int, int> pii;
const int maxn = 2e6 + 10;
const int mod = 998244353;

struct edge {
    int u, v;
    int w[5] = {};
    edge() = default;
    edge(int u, int v, int a, int b, int c, int d): u(u), v(v) { w[1] = a, w[2] = b, w[3] = c, w[4] = d; }
    int& operator[] (int x) { return w[x]; }
};

int n, m, ans;
umap<int, edge> e[maxn]; 
edge ed[maxn];
int tot;
int deg[maxn];
int f[maxn], g[maxn];
int del[maxn];
int que[maxn], hd = 1, tl;
int id[maxn], cnt;
int pos[maxn];

void add_edge(int u, int v, int a, int b, int c, int d) {
    if (e[u].count(v)) {
        (e[u][v][1] *= a) %= mod;
        (e[u][v][2] *= b) %= mod;
        (e[u][v][3] *= c) %= mod;
        (e[u][v][4] *= d) %= mod;
    } else {
        edge cur = edge(u, v, a, b, c, d);
        e[u][v] = cur;
        deg[u]++;
    }
}

void del_edge(int u, int v) {
    e[u].erase(v);
    deg[u]--;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        add_edge(u, v, 0, 1, 1, 1);
        add_edge(v, u, 0, 1, 1, 1);
    }
    for (int i = 1; i <= n; i++) f[i] = g[i] = 1;
    for (int i = 1; i <= n; i++) if (deg[i] <= 2) que[++tl] = i;
    while (hd <= tl) {
        int u = que[hd++]; 
        if (!deg[u]) continue;
        if (deg[u] == 1) {
            edge i = e[u].begin()->second;
            int v = i.v;
            (f[v] *= (f[u] * i[1] % mod + g[u] * i[4] % mod) % mod) %= mod;
            (g[v] *= (f[u] * i[3] % mod + g[u] * i[2] % mod) % mod) %= mod;
            del[u] = true;
            del_edge(u, v), del_edge(v, u);
            if (deg[v] <= 2) que[++tl] = v;
        } else {
            edge i = e[u].begin()->second;
            edge j = next(e[u].begin())->second; 
            int v1 = i.v, v2 = j.v;
            swap(i[3], i[4]);
            edge cur = edge(v1, v2, 
                (i[1] * j[1] % mod * f[u] % mod + i[3] * j[4] % mod * g[u] % mod) % mod,
                (i[4] * j[3] % mod * f[u] % mod + i[2] * j[2] % mod * g[u] % mod) % mod,
                (i[1] * j[3] % mod * f[u] % mod + i[3] * j[2] % mod * g[u] % mod) % mod,
                (i[4] * j[1] % mod * f[u] % mod + i[2] * j[4] % mod * g[u] % mod) % mod
            );
            del[u] = true;
            del_edge(u, v1), del_edge(v1, u);
            del_edge(u, v2), del_edge(v2, u);
            add_edge(cur.u, cur.v, cur[1], cur[2], cur[3], cur[4]);
            add_edge(cur.v, cur.u, cur[1], cur[2], cur[4], cur[3]);
            if (deg[v1] <= 2) que[++tl] = v1;
            if (deg[v2] <= 2) que[++tl] = v2;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!del[i]) {
            id[++cnt] = i;
            pos[i] = cnt;
        }
    }
    for (int u = 1; u <= n; u++) {
        if (del[u]) continue;
        for (pair<int, edge> i : e[u]) if (u < i.second.v) ed[++tot] = i.second;
    }
    for (int S = 0; S < (1ll << cnt); S++) {
        int mul = 1;
        for (int i = 1; i <= cnt; i++) {
            if (S >> i - 1 & 1) (mul *= f[id[i]]) %= mod;
            else (mul *= g[id[i]]) %= mod;
        }
        for (int i = 1; i <= tot; i++) {
            int u = pos[ed[i].u], v = pos[ed[i].v];
            int p = S >> u - 1 & 1, q = S >> v - 1 & 1;
            if (p && q) (mul *= ed[i][1]) %= mod;
            else if (!p && !q) (mul *= ed[i][2]) %= mod;
            else if (p && !q) (mul *= ed[i][3]) %= mod;
            else (mul *= ed[i][4]) %= mod;
        }
        (ans += mul) %= mod;
    }
    cout << ans << endl;
    return 0;
}