专栏文章

题解：P4426 [HNOI/AHOI2018] 毒瘤

CClaire0918
P4426题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxpcn9
此快照首次捕获于
2025/12/02 10:03
3 个月前
此快照最后确认于
2025/12/02 10:03
3 个月前
查看原文
注意到 m−nm - n 非常小，也就是该图是一棵树加上少量非树边。对于非树边 (u,v)(u, v)，考虑 uu 是否选择：若 uu 选择则要求 vv 不选，否则不限制 vv，即可 O(2m−n+1)\mathcal{O}(2^{m - n + 1}) 消除非树边限制。我们在树上设 fu,0/1f_{u, 0/1} 表示 uu 选或不选时 uu 子树内的方案数，就有
fu,0=∏v(fv,0+fv,1)fu,1=∏vfv,0f_{u, 0} = \prod_v (f_{v, 0} + f{v, 1})\\ f_{u, 1} = \prod_v f_{v, 0}\\
直接暴力 DP，时间复杂度 O(n2m−n+1)≈2×108\mathcal{O}(n2^{m - n + 1}) \approx 2 \times 10^8，不能通过。
我们发现每次 DP 有意义的点很少。具体来说，我们对于所有连了非树边的点建虚树，那么对于虚树上一条边 (u,v)(u, v)，其在原树上可能是链 u,x1,x2,…,xt,vu, x_1, x_2, \ldots, x_t, v，显然 xix_i 都只有一个儿子 xi+1x_{i + 1} 的子树在虚树上（否则 xix_i 一定在虚树上），我们记 xix_i 除了 xi+1x_{i + 1} 外的儿子为 {yi}\{y_i\}，于是
fxi,0=(fxi+1,0+fxi+1,1)×∏yj(fyj,0+fyj,1)fxi,1=fxi+1,0×∏yjfyj,0f_{x_i, 0} = (f_{x_{i + 1}, 0} + f_{x_{i + 1}, 1}) \times \prod_{y_j} (f_{y_j, 0} + f_{y_j, 1})\\ f_{x_i, 1} = f_{x_{i + 1}, 0} \times \prod_{y_j} f_{y_j, 0}\\
中后面的积式是不变的，仅有前面一项与 xi+1x_{i + 1} 相关的在不同的 DP 中变化，即 fxif_{x_i} 仅随 fxi+1f_{x_{i + 1}} 变化。归纳一下，fuf_u 仅随 fvf_v 变化，也就是说我们可以直接在虚树上 DP。
这样的变化显然是线性的，我们将那一积式的定值设为 pxi,0/1p_{x_i, 0/1}，设
fxi,0=kxi,0,0fv,0+kxi,0,1fv,1fxi,1=kxi,1,0fv,0+kxi,1,1fv,1f_{x_i, 0} = k_{x_i, 0, 0}f_{v, 0} + k_{x_i, 0, 1}f_{v, 1}\\ f_{x_i, 1} = k_{x_i, 1, 0}f_{v, 0} + k_{x_i, 1, 1}f_{v, 1}\\
那么就有
fxi,0=pxi,0×(fxi+1,0+fxi+1,1)=pxi,0×(kxi+1,0,0fv,0+kxi+1,0,1fv,1+kxi+1,1,0fv,0+kxi+1,1,1fv,1)=fv,0×pxi,0(kxi+1,0,0+kxi+1,1,0)+fv,1×pxi,0(kxi+1,0,1+kxi+1,1,1)fxi,1=pxi,1×fxi+1,0=pxi,1×(kxi+1,0,0fv,0+kxi+1,0,1fv,1)=fv,0×pxi,1kxi+1,0,0+fv,1×pxi,1kxi+1,0,1\begin{aligned} f_{x_i, 0} &= p_{x_i, 0} \times (f_{x_{i + 1}, 0} + f_{x_{i + 1}, 1})\\ &= p_{x_i, 0} \times (k_{x_{i + 1}, 0, 0}f_{v, 0} + k_{x_{i + 1}, 0, 1}f_{v, 1} + k_{x_{i + 1}, 1, 0}f_{v, 0} + k_{x_{i + 1}, 1, 1}f_{v, 1})\\ &= f_{v, 0} \times p_{x_i, 0}(k_{x_{i + 1}, 0, 0} + k_{x_{i + 1}, 1, 0}) + f_{v, 1} \times p_{x_i, 0}(k_{x_{i + 1}, 0, 1} + k_{x_{i + 1}, 1, 1})\\ f_{x_i, 1} &= p_{x_i, 1} \times f_{x_{i + 1}, 0}\\ &= p_{x_i, 1} \times (k_{x_{i + 1}, 0, 0}f_{v, 0} + k_{x_{i + 1}, 0, 1}f_{v, 1})\\ &= f_{v, 0} \times p_{x_i, 1}k_{x_{i + 1}, 0, 0} + f_{v, 1} \times p_{x_i, 1}k_{x_{i + 1}, 0, 1}\\ \end{aligned}
从而
{kxi,0,s=pxi,0(kxi+1,0,s+kxi+1,1,s)kxi,1,s=pxi,1kxi+1,0,s\begin{cases} k_{x_i, 0, s} = p_{x_i, 0}(k_{x_{i + 1}, 0, s} + k_{x_{i + 1}, 1, s})\\ k_{x_i, 1, s} = p_{x_i, 1}k_{x_{i + 1}, 0, s}\\ \end{cases}
还有初始的
kv,x,y=[x=y]k_{v, x, y} = [x = y]
于是我们可以 DFS 建虚树，在建虚树时顺便转移 {ki}\{k_i\}，就可以直接在虚树上做 DP 了。时间复杂度降到 O(n+(n−m+1)2n−m+1)\mathcal{O}(n + (n - m + 1)2^{n - m + 1})，可以通过。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...