P1043策划道路（city）

【题目背景】

能量样本完成入库后，Ehundategh 开始整理主营地与周边聚落之间的道路规划。现有地图上还缺少一处新的补给城市，他需要比较不同接入位置带来的总通行费用。

【题目描述】

地图上原有 $n$ 座城市，编号为 $1\sim n$。这些城市之间存在 $n-1$ 条双向道路，并且任意两座城市之间都能够通过道路相互到达。

通过第 $i$ 条道路需要花费 $w_i$。对于两座城市 $x,y$，定义 $\operatorname{cost}(x,y)$ 为从城市 $x$ 到城市 $y$ 的简单路径上所有道路费用之和。特别地，$\operatorname{cost}(x,x)=0$。

Ehundategh 准备新建编号为 $n+1$ 的城市，并修建一条连接新城市与原有城市的双向道路。他一共准备了 $q$ 份彼此独立的道路方案。

第 $i$ 份道路方案给出两个整数 $k_i,x_i$，表示修建一条连接城市 $k_i$ 与城市 $n+1$、费用为 $x_i$ 的道路。每份道路方案都从原有地图开始计算，不会改变其他方案中的道路。

对于每份道路方案，Ehundategh 希望求出新道路建成后所有有序城市对之间的费用总和。也就是说，对于所有满足 $1\leq x,y\leq n+1$ 的有序对 $(x,y)$，将 $\operatorname{cost}(x,y)$ 全部相加。

答案可能很大，你只需要输出它对 $998{,}244{,}353$ 取模的结果。

【输入格式】

从文件 $\textbf{\textit{city.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示原有城市数量与道路方案数量。

接下来 $n-1$ 行，每行包含三个正整数 $u_i,v_i,w_i$，表示城市 $u_i,v_i$ 之间存在一条费用为 $w_i$ 的双向道路。

接下来 $q$ 行，每行包含两个正整数 $k_i,x_i$，表示一份道路方案。

【输出格式】

输出到文件 $\textbf{\textit{city.out}}$ 中。

对于每份道路方案输出一行一个整数，表示对应费用总和对 $998{,}244{,}353$ 取模的结果。

【样例 1 输入】

10 224 231 2 142 3 252 4 361 273 182 391 2 5101 1112 4121 10

【样例 1 输出】

168264324436560

【说明/提示】

【样例 1 解释】

第一组测试数据中，原有城市间所有有序城市对的费用总和为 $36$。第一份道路方案产生的新增费用为 $32$，因此答案为 $68$。

【样例 2】

见选手目录下的 $\textbf{\textit{city/city2.in}}$ 和 $\textbf{\textit{city/city2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{city/city3.in}}$ 和 $\textbf{\textit{city/city3.ans}}$。

该组样例符合测试点 $4\sim 7$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{city/city4.in}}$ 和 $\textbf{\textit{city/city4.ans}}$。

该组样例符合测试点 $8\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{city/city5.in}}$ 和 $\textbf{\textit{city/city5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{city/city6.in}}$ 和 $\textbf{\textit{city/city6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$2\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$，单个测试点内 $\sum n\leq 2\times 10^5$ 且 $\sum q\leq 2\times 10^5$，$1\leq u_i,v_i,k_i\leq n$，$1\leq w_i,x_i\leq 10^6$。

特殊性质 A：保证每组测试数据中，第 $i$ 条道路均连接城市 $i$ 与城市 $i+1$。

特殊性质 B：保证每份道路方案均满足 $k_i=1$。