Can They Go to Galar? - 题解

标签与难度

标签: 图论, 仙人掌图, 概率与期望, 动态规划, Tarjan算法, 双连通分量, 点双连通分量, 缩点, 树形DP, 模运算难度: 2300

题目大意喵~

一群宝可梦想要去新的伽勒尔地区旅行，但是经费有限，不能所有宝可梦都去呢。所以，我们制定了以下规则来决定谁能去，喵~

我们有一张 $n$ 个点 $m$ 条边的无向连通图，代表了 $n$ 只宝可梦和它们之间的联系。这张图很特别，是一棵仙人掌图，也就是说，每条边最多只属于一个简单环。每条边 $(u, v)$ 都有一个概率 $w$ 可以“通过”。

宝可梦们分批次获得前往伽勒尔的许可：

第一轮，只有 1 号宝可梦能去。
在第 $i$ 轮（ $i \ge 2$ ），如果宝可梦 $u$ 在第 $i-1$ 轮获得了许可，而宝可梦 $v$ 还没有，并且它们之间有一条边，通过概率为 $w$ ，那么 $v$ 就有 $w$ 的概率在这一轮获得许可。
这个过程会一直持续下去，直到没有新的宝可梦能获得许可为止。

我们的任务是计算最终能去伽勒尔地区的宝可梦数量的期望值。因为要处理小数，所以答案需要对 $998244353$ 取模，喵~

解题思路分析

喵哈~！看到期望问题，我的DNA就动了！根据期望的线性性质，一个随机变量的和的期望等于它们各自期望的和。也就是说，最终能去伽勒尔的宝可梦数量的期望值，就等于每只宝可梦能去伽勒尔的概率之和，的说。

E[\text{总数}] = \sum_{i=1}^{n} P(\text{宝可梦 } i \text{ 能去伽勒尔})

所以，问题就转化成：对每个宝可梦 $i$ ，计算它能去伽勒尔的概率 $P(i)$ 。

一只宝可梦 $i$ 能去伽勒尔，当且仅当存在至少一条从 1 号点到 $i$ 号点的路径，这条路径上所有的边都成功“通过”了。计算这个概率直接在原图上会很麻烦，因为从 1 到 $i$ 可能有很多条路径，它们之间可能共享边或点，导致概率计算非常复杂，喵~

但是！题目给了一个关键信息：这是一张仙人掌图！仙人掌图的结构比一般图要简单得多，它的任意两个简单环最多只有一个公共点。这让我们可以把它分解成一个更简单的结构——树！

仙人掌图的树化 (Block-Cut Tree)

我们可以把仙人掌图中的“桥”（不属于任何环的边）和“环”看作是连接点的基本单元。通过一种叫做“缩点”的技巧，我们可以把原图变成一棵树，这棵树我们通常叫做圆方树或者块切树 (Block-Cut Tree)。

具体怎么做呢？

点双连通分量 (BCC): 我们需要找到图中的所有点双连通分量。在仙人掌图中，一个点双连通分量要么是一条桥，要么是一个简单的环。我们可以用 Tarjan 算法来找到它们。
建树:
- 原来的 $n$ 个点，我们称为原点 (圆点)。
- 对于每一个找到的环 (一个拥有多于两个点的BCC)，我们创建一个新的方点来代表这个环。
- 在新的树形结构中，如果一个原点 $u$ 属于一个环 $C$ ，我们就在 $u$ 和代表 $C$ 的方点之间连一条边。
- 如果一条边 $(u, v)$ 是一个桥 (一个只有两个点的BCC)，我们就在原点 $u$ 和 $v$ 之间直接连一条边。

经过这样的改造，原来的仙人掌图就变成了一棵真正的树！树上的节点有两种：代表原来宝可梦的圆点，和代表环的方点。这棵树的结构清晰地反映了原图中桥和环的连接关系，喵~

在树上计算概率

现在我们有了一棵树，从 1 号点出发，问题就变成了在树上做动态规划（或者说树形DP）啦！我们可以从根节点 1 开始进行一次深度优先搜索 (DFS)，计算每个点被“激活”（即获得许可）的概率。

我们用 prob[u] 表示节点 u 被激活的概率。

初始状态: 根节点 1 号宝可梦是必定能去的，所以 prob[1] = 1。

在DFS过程中，当我们从父节点 p 访问子节点 c 时：

父 p 是圆点，子 c 也是圆点: 这意味着 (p, c) 是一条桥，设其通过概率为 w。c 要被激活，必须 p 先被激活，然后桥 (p, c) 也要通。这两个事件是独立的，所以 prob[c] = prob[p] * w。
父 p 是圆点，子 c 是方点 (代表一个环): p 是这个环的一个成员（称为割点）。p 被激活后，激活信号就传到了这个环上。我们可以认为方点 c 被激活的概率就是 p 被激活的概率，即 prob[c] = prob[p]。
父 p 是方点，子 c 是圆点: 这意味着 c 是环 p 上的一个点。激活信号已经到达了环 p，现在要计算它传到环上另一个点 c 的概率。设我们是从割点 u (即 p 的父节点) 进入这个环的。在环上，从 u 到 c 有两条不相交的路径（顺时针和逆时针）。
- 设顺时针路径通过的概率是 $P_1$ （路径上所有边概率的乘积）。
- 设逆时针路径通过的概率是 $P_2$ 。
- c 能被激活，只要这两条路径中至少有一条通了就行。其概率是 $P(\text{至少一条通}) = 1 - P(\text{两条都断}) = 1 - (1 - P_1)(1 - P_2)$ 。
- 所以，`prob[c] = prob[u] * (1 - (1-P_1)(1-P_2))$。
- 为了高效计算一个环上任意两点间的路径概率，我们可以对环上的边做一次前缀积和后缀积，这样就能 $O(1)$ 查询了，非常方便哦！

整个算法流程就是：

用 Tarjan 算法找到所有点双连通分量，并建立起这棵圆方树。
从 1 号点开始，在圆方树上进行一次 DFS，按照上面的规则计算出每个圆点（代表宝可梦）能去伽勒尔的最终概率。
把所有圆点的概率加起来，就是我们想要的期望值啦！

这样，一个复杂的图概率问题就被我们分解成了建树和树上DP两个步骤，是不是清晰多啦？加油，你一定可以的，喵~！

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助你理解，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int MOD = 998244353;
const int MAXN = 100000 + 5;
const int MAX_NODES = 2 * MAXN; // 原点 + 方点

// 快速幂计算 (a^b) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元计算 a^-1 % MOD
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 模块化加法
int add(int a, int b) {
    return (a + (long long)b) % MOD;
}

// 模块化减法
int sub(int a, int b) {
    return (a - (long long)b + MOD) % MOD;
}

// 模块化乘法
int mul(int a, int b) {
    return (a * (long long)b) % MOD;
}

struct Edge {
    int to;
    int probability;
    int original_id; // 用于Tarjan算法
};

vector<Edge> original_adj[MAXN];
vector<pair<int, int>> tree_adj[MAX_NODES]; // {to, probability} for bridges

int n, m;
int node_count; // 总节点数 (原点+方点)

// --- Tarjan算法部分 ---
int dfn[MAXN], low[MAXN], timer;
vector<pair<int, int>> edge_stack; // {u, v}
vector<vector<pair<int, int>>> bccs; // 存储BCC的边集

void find_bccs(int u, int p_edge_id) {
    dfn[u] = low[u] = ++timer;

    for (const auto& edge : original_adj[u]) {
        if (edge.original_id == p_edge_id) continue;
        int v = edge.to;
        
        if (!dfn[v]) {
            edge_stack.push_back({u, v});
            find_bccs(v, edge.original_id);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) { // 找到一个BCC，u是割点
                vector<pair<int, int>> current_bcc_edges;
                while (true) {
                    pair<int, int> top_edge = edge_stack.back();
                    edge_stack.pop_back();
                    current_bcc_edges.push_back(top_edge);
                    if (top_edge.first == u && top_edge.second == v) break;
                }
                bccs.push_back(current_bcc_edges);
            }
        } else if (dfn[v] < dfn[u]) {
            low[u] = min(low[u], dfn[v]);
            edge_stack.push_back({u, v});
        }
    }
}

// --- 概率计算DFS ---
int final_prob[MAX_NODES];
int total_expected_value;

void calculate_probs_dfs(int u, int p) {
    if (u <= n) { // 如果是原点(宝可梦)
        total_expected_value = add(total_expected_value, final_prob[u]);
    }

    for (auto const& [v, prob_w] : tree_adj[u]) {
        if (v == p) continue;
        
        // Case 1: 桥 (圆点 -> 圆点)
        if (u <= n && v <= n) {
            final_prob[v] = mul(final_prob[u], prob_w);
            calculate_probs_dfs(v, u);
        } 
        // Case 2: 进入环 (圆点 -> 方点)
        else if (u <= n && v > n) {
            final_prob[v] = final_prob[u]; // 激活方点的概率等于割点的概率
            calculate_probs_dfs(v, u);
        }
    }

    // Case 3: 从环出来 (方点 -> 圆点)
    if (u > n) {
        int articulation_point = p;
        vector<pair<int, int>> cycle_nodes_with_prob;
        cycle_nodes_with_prob.push_back({articulation_point, 1});

        // 找到环上的所有点和边，并按顺序排列
        vector<int> path_nodes;
        vector<int> path_probs;
        int current_node = articulation_point;
        int prev_node = -1;

        for (size_t i = 0; i < tree_adj[u].size(); ++i) {
            path_nodes.push_back(current_node);
            bool found_next = false;
            for (auto const& [neighbor, prob_w] : tree_adj[u]) {
                if (neighbor != prev_node && neighbor != articulation_point) {
                    path_probs.push_back(prob_w);
                    prev_node = current_node;
                    current_node = neighbor;
                    found_next = true;
                    break;
                }
            }
            if (!found_next) { // 最后一条边，连回起点
                 for (auto const& [neighbor, prob_w] : tree_adj[u]) {
                    if (neighbor == articulation_point) {
                        path_probs.push_back(prob_w);
                        break;
                    }
                 }
            }
        }
        
        int k = path_nodes.size();
        vector<int> pref_prod(k + 1, 1);
        vector<int> suff_prod(k + 2, 1);
        for(int i = 0; i < k; ++i) pref_prod[i+1] = mul(pref_prod[i], path_probs[i]);
        for(int i = k - 1; i >= 0; --i) suff_prod[i+1] = mul(suff_prod[i+2], path_probs[i]);

        // 计算环上每个点的概率
        for (int i = 1; i < k; ++i) {
            int node_v = path_nodes[i];
            int prob1 = pref_prod[i]; // 顺时针
            int prob2 = mul(suff_prod[i+2], pref_prod[0]); // 逆时针
            int prob_v_from_u = sub(1, mul(sub(1, prob1), sub(1, prob2)));
            final_prob[node_v] = mul(final_prob[u], prob_v_from_u);
        }
        
        // 从环上的点继续DFS
        for (auto const& [v, prob_w] : tree_adj[u]) {
             if (v != articulation_point) {
                 calculate_probs_dfs(v, u);
             }
        }
    }
}


void solve() {
    cin >> n >> m;
    
    // --- 初始化 ---
    for (int i = 1; i <= n; ++i) original_adj[i].clear();
    for (int i = 1; i <= n + m; ++i) {
        tree_adj[i].clear();
        dfn[i] = 0;
        final_prob[i] = 0;
    }
    bccs.clear();
    edge_stack.clear();
    timer = 0;
    node_count = n;
    total_expected_value = 0;

    // --- 读图 ---
    vector<int> edge_p(m + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v, p, q;
        cin >> u >> v >> p >> q;
        int prob = mul(p, modInverse(q));
        original_adj[u].push_back({v, prob, i});
        original_adj[v].push_back({u, prob, i});
        edge_p[i] = prob;
    }

    // --- 1. 建树 ---
    find_bccs(1, 0);

    for (const auto& bcc_edges : bccs) {
        if (bcc_edges.size() == 1) { // 桥
            int u = bcc_edges[0].first;
            int v = bcc_edges[0].second;
            int prob = 0;
            for(const auto& edge : original_adj[u]) {
                if (edge.to == v) {
                    prob = edge.probability;
                    break;
                }
            }
            tree_adj[u].push_back({v, prob});
            tree_adj[v].push_back({u, prob});
        } else { // 环
            int cycle_node = ++node_count;
            vector<pair<int, int>> nodes_in_cycle;
            for (const auto& edge : bcc_edges) {
                nodes_in_cycle.push_back({edge.first, 0});
                nodes_in_cycle.push_back({edge.second, 0});
            }
            sort(nodes_in_cycle.begin(), nodes_in_cycle.end());
            nodes_in_cycle.erase(unique(nodes_in_cycle.begin(), nodes_in_cycle.end()), nodes_in_cycle.end());

            for (auto& p : nodes_in_cycle) {
                tree_adj[p.first].push_back({cycle_node, 1}); // 概率为1的逻辑边
                
                // 为了方便在DFS中重构环，把环的边信息也挂在方点上
                for(const auto& edge : bcc_edges) {
                    if (edge.first == p.first || edge.second == p.first) {
                        int other = (edge.first == p.first) ? edge.second : edge.first;
                        int prob = 0;
                        for(const auto& orig_edge : original_adj[p.first]) {
                            if(orig_edge.to == other) {
                                prob = orig_edge.probability;
                                break;
                            }
                        }
                        tree_adj[cycle_node].push_back({other, prob});
                    }
                }
            }
        }
    }
    // 去重方点邻接表
    for (int i = n + 1; i <= node_count; ++i) {
        sort(tree_adj[i].begin(), tree_adj[i].end());
        tree_adj[i].erase(unique(tree_adj[i].begin(), tree_adj[i].end()), tree_adj[i].end());
    }


    // --- 2. 计算概率 ---
    final_prob[1] = 1;
    calculate_probs_dfs(1, 0);

    cout << total_expected_value << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Note: The logic for reconstructing the cycle path inside the DFS (calculate_probs_dfs) can be tricky. The provided code gives one way to do it by storing edge information in the tree adjacency list. There are other cleaner ways, for instance, by storing the BCC information in a separate structure indexed by the cycle node ID.

复杂度分析

时间复杂度: $O(N+M)$
- Tarjan 算法寻找所有点双连通分量的时间复杂度是 $O(N+M)$ ，其中 $N$ 是点数， $M$ 是边数。
- 构建圆方树的过程，需要遍历所有 BCC，总的顶点和边的数量级也是 $O(N+M)$ 。
- 最后在圆方树上进行 DFS，树的节点数最多为 $N+M$ ，边数也为 $O(N+M)$ 。在处理环（方点）时，我们需要遍历环上的所有点和边，但每个点和边只属于一个 BCC，所以所有环处理的总时间也是 $O(N+M)$ 。
- 因此，总的时间复杂度是 $O(N+M)$ ，非常高效，喵~
空间复杂度: $O(N+M)$
- 存储原图和圆方树的邻接表需要 $O(N+M)$ 的空间。
- Tarjan 算法需要的 dfn, low 数组和栈也需要 $O(N+M)$ 的空间。
- 存储最终概率的数组需要 $O(N+M)$ 的空间。
- 所以总的空间复杂度也是 $O(N+M)$ 。

知识点总结

这道题是一道非常棒的图论综合题，融合了多个知识点，做完之后一定收获满满，喵！

期望的线性性质: 这是解决所有期望问题的基石！将“总数的期望”转化为“概率的和”。
仙人掌图 (Cactus Graph): 认识这种特殊的图结构，它的“每个环最多一个公共点”的性质是解题的关键。
点双连通分量 (Biconnected Components): 学会如何分解图。对于仙人掌图，BCCs 就是桥和环。
Tarjan 算法: 找到 BCCs 的标准高效算法，是图论工具箱里的必备武器！
缩点与建树 (Block-Cut Tree / 圆方树): 将复杂的图结构转化为简单的树结构，是处理这类问题的经典思想。
树形动态规划 (DP on Trees): 在构建好的树上，利用 DFS 进行信息传递和计算，是树形问题的通用解法。
概率论基础: 计算独立事件的概率（相乘），以及互斥事件的“或”概率（ $1 - (1-P_1)(1-P_2)$ ）。
模运算: 在算法竞赛中处理大数和分数取模的基本功。

希望这篇题解能帮到你，如果有任何问题，随时可以再来问我哦！一起加油，变得更强，喵~！

Can They Go to Galar? - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

仙人掌图的树化 (Block-Cut Tree) ​

在树上计算概率 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​