题解：「USACO 2024 Jan Platinum P1」Island Vacation（含完整代码+逐行解析）

核心思路总览

本题是 仙人掌图上的概率DP问题，核心通过“缩环建块 + 两次DFS递推概率”求解。先将仙人掌图按环结构缩成“块树”（每个块是环或单点树），再通过两次DFS分别计算块内概率转移系数和节点最终结束概率，最终复杂度 (O(N + M))，适配 (10^4) 规模数据。

关键背景与图结构处理

1. 仙人掌图特性

题目中“无桥属于多个简单环”的条件，对应图论中的仙人掌图。其核心特性是：任意两个简单环最多共享一个节点，可分解为“树 + 环”的组合结构，适合通过“缩环”转化为树状结构处理。

2. 缩环建块（tarjan 函数）

通过 Tarjan 算法识别环结构，将每个环缩成“超级节点”（块），构建块树 G：

• 超级节点编号从 (n+1) 开始（vc = n 为初始值）。
• 块树中，每个块（超级节点）的子节点是环上的原始节点；原始节点的子节点是其相邻的块（或单点树）。
• 例如：环 (1-2-3-1) 缩成超级节点 (4)，G[4] = [1,2,3]，G[1], G[2], G[3] 包含超级节点 (4)。

核心状态定义

完整代码（带关键注释）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 20005, MOD = 1e9 + 7;

vector <int> E[MAXN], G[MAXN];  // E：原始图邻接表；G：缩环后的块树邻接表
int n, m, vc, d[MAXN];          // vc：超级节点（块）数量；d[i]：原始节点i的度数
int dfn[MAXN], low[MAXN], dcnt, st[MAXN], tp;  // Tarjan用：时间戳、栈、栈顶
bool ins[MAXN];                  // 标记节点是否在栈中（Tarjan找环）

// Tarjan算法：找环并缩环建块树G
void tarjan(int u) {
    dfn[u] = low[u] = ++dcnt;    // 初始化时间戳
    st[++tp] = u; ins[u] = true; // 节点入栈，标记在栈中

    for (int v : E[u]) {
        if (!dfn[v]) {            // 未访问过的子节点
            tarjan(v);
            low[u] = min(low[u], low[v]);  // 更新low值

            // 找到一个环的根（low[v] >= dfn[u]表示u是环的起点）
            if (low[v] >= dfn[u]) {
                vc++;  // 新建超级节点（块）
                G[u].push_back(vc);  // 父节点u连接到新块
                // 栈中弹出环上节点，全部加入新块的子节点
                for (ins[v] = false; st[tp] != v; tp--) {
                    ins[st[tp]] = false;
                    G[vc].push_back(st[tp]);
                }
                G[vc].push_back(v); tp--;  // 弹出v并加入块
            }
        } else if (ins[v]) {       // 访问过且在栈中（回边，更新low值）
            low[u] = min(low[u], dfn[v]);
        }
    }
}

ll inv[MAXN];  // 模MOD的逆元（预处理用于除法）
ll p[MAXN];    // 继续旅行的概率（补集）
ll f[MAXN];    // 到达概率（从起点1传递到节点u的概率）
ll g[MAXN];    // 回归概率（遍历子块后回到u的概率）
ll h[MAXN];    // 转移系数（块x相对于父节点的传递系数）
ll w[MAXN];    // 临时数组：存储组合数相关的概率累积
ll e[MAXN];    // 自身结束概率（节点u直接结束的贡献）

// 第一次DFS：计算g（回归概率）、h（转移系数）、e（自身结束概率）
void dfs1(int u, int fz) {  // u：当前块/节点；fz：父块（避免回退）
    int k = 0;
    w[0] = 1;  // w[0]初始化1（组合数累积的基准）

    // 第一步：递归处理所有子块（先处理子节点，再计算当前节点）
    for (int x : G[u]) {
        for (int v : G[x]) {  // G[x]是块x的子节点（原始节点）
            dfs1(v, x);       // 递归处理原始节点v
        }
    }

    // 第二步：计算所有子块的回归概率乘积（用于组合数累积）
    for (int x : G[u]) {
        if (G[x].size() > 1) {  // x是超级节点（环块）
            g[x] = 1;
            // 环块x的回归概率 = 所有子节点回归概率的乘积
            for (int v : G[x]) {
                g[x] = g[x] * g[v] % MOD;
            }
            w[++k] = 0;  // k记录环块数量，w数组扩展
        }
    }

    // 第三步：计算当前节点u的回归概率g[u]（基于组合数和逆元）
    int dg = d[u] - (u > 1);  // u的有效度数：总度数 - 父边（u>1时存在父边）
    ll c = inv[dg] * p[u] % MOD;  // 初始概率：1/dg（选边概率） * p[u]（继续旅行）
    for (int i = 0; i <= k; ++i) {
        g[u] = (g[u] + c * w[i]) % MOD;  // 累积回归概率
        if (i < k) {  // 更新c：组合数递推（处理多个环块的选择）
            c = c * 2 % MOD;
            c = c * inv[dg - 2 * i - 2] % MOD;
            c = c * (i + 1) % MOD;
            c = c * p[u] % MOD;
        }
    }

    // 第四步：计算转移系数h[x]（父节点到块x的概率传递）
    for (int x : G[u]) {
        if (G[x].size() > 1) {  // x是环块
            ll z = 1;
            c = inv[dg] * p[u] % MOD;
            for (int i = 0; i < k; ++i) {
                h[x] = (h[x] + c * z) % MOD;  // 累积转移系数
                // 更新c和z（组合数递推）
                c = c * 2 % MOD;
                c = c * inv[dg - 2 * i - 2] % MOD;
                c = c * (i + 1) % MOD;
                c = c * p[u] % MOD;
                z = (w[i + 1] + (MOD - g[x]) * z) % MOD;
            }
        } else {  // x是单点树（非环块）
            h[x] = g[u];  // 转移系数 = 父节点的回归概率
        }
    }

    // 第五步：计算自身结束概率e[u]
    if (G[fz].size() > 1) {  // 父块是环块
        e[u] = (1 + MOD - g[u]) % MOD;  // 1 - 回归概率（不回归则结束）
    } else {
        e[u] = 1;  // 父块是单点，初始结束概率1
    }
    // 累积子块对e[u]的贡献
    for (int x : G[u]) {
        if (G[x].size() > 1) {  // x是环块
            e[u] = (e[u] + h[x] * 2 % MOD * (g[x] + MOD - 1) % MOD) % MOD;
        } else {  // x是单点
            e[u] = (e[u] + MOD - h[x]) % MOD;
        }
    }
}

// 第二次DFS：计算到达概率f[u]，并传递到子节点
void dfs2(int u) {
    for (int x : G[u]) {
        if (G[x].size() == 1) {  // x是单点树（子节点是原始节点）
            int v = G[x][0];
            f[v] = f[u] * h[x] % MOD;  // 到达概率 = 父到达概率 * 转移系数
            dfs2(v);  // 递归处理子节点
            continue;
        }

        // x是环块：向环上所有节点传递到达概率（双向遍历）
        ll z = f[u] * h[x] % MOD;
        // 正向遍历环上节点，传递概率
        for (int i = 0; i < (int)G[x].size(); ++i) {
            f[G[x][i]] = (f[G[x][i]] + z) % MOD;
            z = z * g[G[x][i]] % MOD;  // 乘回归概率，传递到下一个节点
        }
        // 反向遍历环上节点，传递概率
        z = f[u] * h[x] % MOD;
        for (int i = G[x].size() - 1; ~i; --i) {
            f[G[x][i]] = (f[G[x][i]] + z) % MOD;
            z = z * g[G[x][i]] % MOD;
        }

        // 递归处理环上每个节点的子块
        for (int v : G[x]) {
            dfs2(v);
        }
    }
}

// 每组测试用例的求解入口
void solve() {
    cin >> n >> m;
    vc = n;  // 超级节点从n+1开始编号
    dcnt = tp = 0;  // 重置Tarjan相关变量

    // 读取p数组，并转换为“继续旅行的概率”（补集）
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        p[i] = (1 + MOD - p[i]) % MOD;  // 1 - 结束概率 = 继续概率
    }

    // 读取原始图，初始化邻接表E和度数d
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
        ++d[u]; ++d[v];
    }

    // 1. Tarjan缩环建块树
    tarjan(1);
    // 2. 第一次DFS：计算g、h、e
    dfs1(1, 0);
    // 3. 初始化起点1的到达概率为1
    f[1] = 1;
    // 4. 第二次DFS：计算所有节点的到达概率f
    dfs2(1);

    // 输出答案：e[u] * f[u] mod MOD
    for (int i = 1; i <= n; ++i) {
        cout << e[i] * f[i] % MOD << " \n"[i == n];
    }

    // 重置所有数组（多测试用例）
    for (int i = 1; i <= n; ++i) {
        E[i].clear();
        d[i] = 0;
        dfn[i] = low[i] = ins[i] = 0;
    }
    for (int i = 1; i <= vc; ++i) {
        e[i] = w[i] = f[i] = g[i] = h[i] = 0;
        G[i].clear();
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // 预处理模MOD的逆元（1~MAXN）
    inv[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }

    int _;
    cin >> _;
    while (_--) {
        solve();
        // 处理测试用例间的空行（题目输入要求）
        string s;
        getline(cin, s);
        if (s.empty()) getline(cin, s);
    }

    return 0;
}

核心流程拆解

1. 预处理逆元

由于概率计算涉及除法（如均匀选择桥的概率 (1/dg)），预处理 (1 \sim MAXN) 的模逆元，将除法转化为乘法（(a/b \mod MOD = a \times inv[b] \mod MOD)）。

2. Tarjan缩环建块

通过Tarjan算法识别环，将每个环缩成超级节点，构建块树 G。块树中仅包含“原始节点-超级节点”的连接，消除环结构的循环依赖，转化为树状结构便于DP。

3. 第一次DFS（dfs1）：计算基础概率系数

• 递归处理所有子块，先计算子节点的回归概率 g。
• 基于组合数和逆元，计算当前节点/块的回归概率 g[u]（考虑所有子块的组合选择）。
• 计算转移系数 h[x]，表示父节点的概率如何传递到子块 x。
• 计算自身结束概率 e[u]，即节点 u 不回归父节点时的结束概率贡献。

4. 第二次DFS（dfs2）：传递到达概率

• 从起点 1 出发（f[1] = 1），将到达概率通过转移系数 h 传递到所有子节点。
• 对于环块，双向遍历环上节点，确保概率均匀传递到每个环上节点。
• 最终每个节点的结束概率 = 自身结束概率 e[u] × 到达概率 f[u]。

关键难点解析

1. 环块的概率处理

环块的概率传递需要双向遍历（正向+反向），因为环上节点可从两个方向被到达，需累积两次传递的概率。

2. 组合数递推

多个环块的选择存在组合关系（如选择k个环块的顺序不影响结果），通过 w 数组累积组合数相关的概率，结合逆元实现高效计算。

3. 模运算处理

所有概率计算均在模 (10^9+7) 下进行，通过补集概率 p[i] 避免减法出现负数，逆元确保除法的正确性。

复杂度分析

• Tarjan缩环：(O(N + M))，每个节点和边仅访问一次。
• 两次DFS：每个节点和块仅处理一次，复杂度 (O(N + M))。
• 整体复杂度 (O(N + M))，适配题目中 (N \leq 10^4)、(M \leq 1.5 \times 10^4) 的规模。