P8331 [ZJOI2022] Easy Problem

Jiutiao Keliang is a girl who likes to create easy problems. As the name suggests, an easy problem contains a lot of the word “easy”. Keliang first gives a simple connected undirected graph, where each edge has a positive integer weight. In particular, Keliang guarantees that the sum of edge weights on any two simple cycles in the graph is equal. Later, Keliang wants to hide this nice property of the graph, so she changes the weights of some edges to new values. Therefore, after the modification, the original nice property may no longer hold. Now she gives the modified graph, along with multiple queries. In each query, you need to find the sum of the weights of all simple paths between two nodes $S, T$. Since the answer may be very large, you only need to output the result modulo $998244353$. Specifically, a simple graph means there are no multiple edges and no self-loops. A simple cycle and a simple path mean they do not contain repeated vertices.

The first line contains three integers $n, m, q$. The next $m$ lines each contain three integers $u, v, w$, representing an undirected edge $(u, v)$ with weight $w$. The next $q$ lines contain $q$ queries. Each query consists of one line with two integers $S, T$.

For each query, output one line with one integer, representing the answer modulo $998244353$.

For all testdata, it holds that $1 \le n, q \le 5 \times {10}^5$, $n - 1 \le m \le 6.4 \times {10}^5$, $1 \le u, v, S, T \le n$, $1 \le w \le {10}^6$. There are no multiple edges or self-loops, and the graph is connected. The specific limits for each test point are shown in the table below: | Test Point ID | Special Constraint 1 | Special Constraint 2 | |:-:|:-:|:-:| | $1$ | $m < n$ | It is guaranteed that there exists a simple path that passes through all vertices. | | $2$ | $m < n$ | None. | | $3 \sim 5$ | No vertex belongs to $\ge 2$ simple cycles. | It is guaranteed that there exists a simple path that passes through all vertices. | | $6 \sim 8$ | No vertex belongs to $\ge 2$ simple cycles. | None. | | $9 \sim 14$ | None. | It is guaranteed that there exists a simple path that passes through all vertices. | | $15 \sim 20$ | None. | None. | Translated by ChatGPT 5