问题重述

给定一个连通无向图，原图具有特殊性质：任意两个简单环的边权和相等。现在部分边权被修改，给出修改后的图，需要回答 $q$ 个查询：对于两点 $S, T$，输出所有简单路径的权值和（模 $998244353$）。

---

关键观察

1. 原图性质分析

原图中所有简单环的边权和相等，设为 $C$。这是一个极强的性质，说明图具有类似「环空间维数很小」的结构。

2. 图的结构分析

设图的环空间的秩为 $k$（即图的第一 Betti 数），那么：

• 如果 $k = 0$，图是树，任意两点间只有一条简单路径
• 如果 $k = 1$，图是基环树（只有一个环）
• 如果 $k \geq 2$，但所有环的权值和相等，说明图具有特殊的对称性

---

核心解法

1. 生成树分解

任取图的一棵生成树 $T$，设非树边集合为 $E'$。

对于原图（修改前），设：

• 非树边 $e \in E'$ 的权值为 $w_e$
• 非树边 $e$ 与树 $T$ 形成的环的权值和为 $C$（对所有 $e$ 相同）

那么有：对于非树边 $e$，设它在树 $T$ 上对应的路径为 $P_e$，则：

$$w_e + \sum_{f \in P_e} w_f = C$$

2. 修改后的影响

修改后，边权可能发生变化。设：

• 修改后的边权为 $w'_e$
• 环的权值和可能不再相等

但原图的性质为我们提供了重要的结构信息。

---

算法框架

1. 路径计数分析

对于两点 $S, T$，设树 $T$ 上从 $S$ 到 $T$ 的路径为 $P_0$，权值和为 $W_0$。

其他简单路径可以通过在 $P_0$ 的基础上「绕环」得到。具体来说：

• 选择一些非树边 $e_1, e_2, \dots, e_k$
• 每条非树边 $e_i$ 对应树上的一个环
• 路径 = $P_0 \oplus$（这些环的对称差）

其中 $\oplus$ 表示边的对称差。

2. 权值计算

设选择了非树边集合 $E_s \subseteq E'$，那么路径权值为：

$$W = W_0 + \sum_{e \in E_s} (w'_e - \text{树上对应路径的权值和}) $$

更精确地说，如果非树边 $e = (u,v)$，树上路径 $P_e$ 从 $u$ 到 $v$，那么：

• 原路径：走 $P_e$，权值和 = $\sum_{f \in P_e} w'_f$
• 新路径：走边 $e$，权值和 = $w'_e$
• 差值：$\Delta_e = w'_e - \sum_{f \in P_e} w'_f$

3. 所有路径的和

所有简单路径的权值和 = $\sum_{E_s \subseteq E'} \left(W_0 + \sum_{e \in E_s} \Delta_e\right)$

设 $|E'| = k$，则：

$$\text{总权值和} = 2^k \cdot W_0 + 2^{k-1} \cdot \sum_{e \in E'} \Delta_e $$

解释：

• 有 $2^k$ 个子集 $E_s$，每个都包含 $W_0$，所以贡献 $2^k W_0$
• 对于固定的 $e$，有 $2^{k-1}$ 个子集包含 $e$，所以 $\Delta_e$ 的总贡献是 $2^{k-1} \Delta_e$

---

具体实现

1. 预处理步骤

1. 找生成树：用 DFS 或 BFS 找一棵生成树 $T$
2. 计算树上路径：
   • 以某个根节点做 DFS，计算每个节点到根的路径权值和 $dist[u]$
   • $S$ 到 $T$ 的树上路径权值 = $dist[S] + dist[T] - 2 \cdot dist[LCA(S,T)]$
3. 处理非树边：
   • 对于每条非树边 $e = (u,v)$，计算 $\Delta_e = w'_e - (dist[u] + dist[v] - 2 \cdot dist[LCA(u,v)])$

2. 查询处理

对于查询 $S, T$：

1. 计算树上路径权值 $W_0$
2. 计算 $\text{总权值和} = 2^k \cdot W_0 + 2^{k-1} \cdot \sum_{e \in E'} \Delta_e \pmod{998244353}$

---

正确性分析

1. 为什么包含所有简单路径？

在无向连通图中，任意两点间的简单路径可以通过在生成树路径的基础上，选择一些非树边对应的环进行「绕路」得到。

2. 为什么不会重复计数？

不同的非树边集合对应不同的简单路径，因为对称差运算保证路径不重复。

---

复杂度分析

• 预处理：
  • 找生成树：$O(n + m)$
  • LCA 预处理：$O(n \log n)$
  • 计算 $\Delta_e$：$O(m)$
• 每个查询：$O(1)$（假设已预处理 $\sum \Delta_e$）
• 总复杂度：$O(n \log n + m + q)$，适合数据范围

---

特殊情况处理

1. 树的情况 ($m = n-1$)

此时 $k = 0$，只有一条简单路径，答案就是树上路径权值。

2. 基环树 ($m = n$)

此时 $k = 1$，公式简化为：

$$\text{总权值和} = 2W_0 + \Delta_{e_1}$$

3. 自环查询 ($S = T$)

此时 $W_0 = 0$，但根据题意，单个节点不算简单路径，答案应为 $0$。

---

模运算处理

由于 $n, m$ 很大，$2^k$ 可能很大，需要预处理 $2$ 的幂次模 $998244353$。

---

总结

这道题的核心在于：

1. 利用原图性质：所有环权值相等的特殊性质提供了重要的结构信息
2. 生成树分解：将图分解为树和非树边，简化路径分析
3. 组合计数：通过非树边子集枚举所有简单路径
4. 高效查询：预处理后每个查询可在 $O(1)$ 时间回答

通过深入分析图的结构性质，我们将复杂的「所有简单路径和」问题转化为简洁的组合计数公式，得到了高效的解法。