题解

问题分析

题目要求计算仙人掌图（每条边最多在一个简单环上）中，从每个节点出发随机游走至任意出口的期望经过边数。随机游走规则为：从当前节点等概率选择相邻边移动，出口的期望步数为0，非出口节点的期望需满足线性方程。

核心思路

1. 期望方程建模：设 ( E[u] ) 为从节点 ( u ) 出发的期望步数。对于出口 ( u )，( E[u] = 0 )；对于非出口 ( u )，设其度数为 ( d[u] )，则： [ E[u] = 1 + \frac{1}{d[u]} \sum_{v \in \text{adj}[u]} E[v] ] 这是一个线性方程组，需求解非出口节点的 ( E[u] )。

2. 仙人掌图的分解：利用 Tarjan 算法识别图中的桥（不在环上的边）和环（简单环）。仙人掌图可分解为“环”和“桥连接的树结构”，便于分层次处理方程。

3. 动态规划维护线性关系：对于每个节点 ( u )，用三元组 ( (a, b, c) ) 表示 ( E[u] ) 与父节点期望的线性关系（如 ( E[u] = a \cdot E[\text{fa}] + b \cdot \text{其他项} + c )）。通过遍历图，动态更新这些系数，将环和桥的影响转化为线性关系，避免直接求解高维方程组。

4. 模运算处理：所有运算在模 ( 998244353 ) 下进行，除法通过乘以逆元（( qpow ) 函数）实现。

详细步骤

1. 图的预处理与出口标记

• 读入图结构（节点、边、出口），标记出口节点（( vis[u] = 1 )，其 ( E[u] = 0 )）。

2. Tarjan 算法分解环与桥

• 通过 DFS 计算每个节点的 ( dfn )（深度优先编号）和 ( low )（最低可达节点编号），识别桥（( low[v] > dfn[u] )）和环（( low[v] = dfn[u] )）。
• 用栈 ( stk ) 记录当前路径，便于提取环上的节点。

3. 动态规划计算线性系数（( dp ) 数组）

• 对于非出口节点 ( u )，初始化 ( dp[u] = (1, 0, 1) )，表示初始方程 ( E[u] = 1 + \sum (\dots) )。
• 处理桥连接的子节点 ( v )：直接更新 ( dp[u] ) 的系数，反映 ( E[u] ) 与 ( E[v] ) 的依赖关系。
• 处理环：遍历环上所有节点，联立其方程，将环的整体影响转化为线性系数，存储在 ( G[u] ) 中（表示 ( u ) 与环内节点的线性关系）。

4. 计算最终期望（( calc ) 函数）

• 从根节点（代码中为节点1）出发，根据 ( G ) 中存储的线性关系，递归计算每个节点的期望 ( ans[u] )，即 ( E[u] ) 的值。

代码解析

• Tarjan 分解：dfs 函数通过 ( dfn ) 和 ( low ) 识别环和桥，用栈提取环节点，将复杂的环关系转化为线性系数。
• 线性系数维护：dp[u].a, dp[u].b, dp[u].c 分别表示线性关系的系数，通过模逆元处理除法，确保方程转化的正确性。
• 期望计算：calc 函数根据 ( G ) 中存储的线性关系，从根节点递归计算所有节点的期望，最终输出结果。

复杂度分析

• 时间复杂度：( O(n + m) )。Tarjan 算法和 DFS 遍历均为线性时间，环的处理每个节点仅参与一次，整体复杂度线性。
• 空间复杂度：( O(n + m) )，用于存储图结构、DFS 栈、线性系数及中间结果。

该方案利用仙人掌图的结构特性和线性关系转化，高效求解随机游走的期望步数，适用于大规模数据。