P9584 「MXOI Round 1」城市

小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。 F 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。 当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。 我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。 为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。 他共有 $q$ 个新建道路的方案，每个方案会给定两个参数 $k_i,w_i$；对于每一个方案，你需要求出在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$。 由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。 **方案之间相互独立**，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。

无

无

#### 【样例解释 #1】 在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：  例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。 容易求得此时 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$。 #### 【样例 #3】 见附加文件中的 `city/city3.in` 与 `city/city3.ans`。 该样例满足测试点 $4$ 的限制。 #### 【样例 #4】 见附加文件中的 `city/city4.in` 与 `city/city4.ans`。 该样例满足测试点 $11$ 的限制。 #### 【样例 #5】 见附加文件中的 `city/city5.in` 与 `city/city5.ans`。 该样例满足测试点 $14$ 的限制。 #### 【样例 #6】 见附加文件中的 `city/city6.in` 与 `city/city6.ans`。 该样例满足测试点 $20$ 的限制。 #### 【数据范围】 对于 $100\%$ 的数据，$2 \le n \le 2\times10^5$，$1 \le q \le 2\times10^5$，$1 \le u_i,v_i,k_i \le n$，$1 \le c_i,w_i \le 10^6$，保证从任意一个城市出发，都能通过原本存在的 $n-1$ 条双向道路，到达任意一个城市。 |测试点编号|$n \le$|$q \le$|特殊性质| |:---:|:---:|:---:|:---:| |$1\sim3$|$80$|$80$|无| |$4\sim7$|$5000$|$5000$|无| |$8\sim10$|$5000$|$2\times10^5$|无| |$11\sim13$|$2\times10^5$|$2\times10^5$|A| |$14\sim16$|$2\times10^5$|$2\times10^5$|B| |$17\sim20$|$2\times10^5$|$2\times10^5$|无| 特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $u_i=i,v_i=i+1$。 特殊性质 B：保证对于所有的 $1 \le i \le q$，都有 $k_i=1$。