#1474. 「MXOI Round 1」城市

「MXOI Round 1」城市

题目描述

小 C 是 F 国的总统,尽管这个国家仅存在于网络游戏中,但他确实是这个国家的总统。

F 国由 nn 个城市构成,这 nn 个城市之间由 n−1n-1 条双向道路互相连接。保证从任意一个城市出发,都能通过这 n−1n-1 条双向道路,到达任意一个城市。

当然,通过这些双向道路是要收费的。通过第 ii 条双向道路,需要花费 cic_i 元。我们称 cic_i 为第 ii 条双向道路的费用。

我们定义 cost(x,y)cost(x,y) 表示从城市 xx 到城市 yy 的简单路径上,所有经过的双向道路的费用之和。特殊地,当 x=yx=y 时,cost(x,y)=0cost(x,y)=0。

为了促进 F 国发展,小 C 新建了一个城市 n+1n+1。现在他需要再新建一条双向道路,使得城市 n+1n+1 也可以通过这 nn 条双向道路到达任意一个城市。

他共有 qq 个新建道路的方案,每个方案会给定两个参数 ki,wik_i,w_i;对于每一个方案,你需要求出在新建一条连接城市 kik_i 和城市 n+1n+1 且费用为 wiw_i 的双向道路后,所有 cost(i,j)cost(i,j) 之和,即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$。

由于答案可能很大,所以你只需要输出答案对 998244353998244353 取模的结果。

方案之间相互独立,也就是说所有方案不会影响现有的道路,这些方案不会真正被施行。

输入格式

第一行两个整数 n,qn,q。

接下来 n−1n-1 行,第 ii 行三个整数 ui,vi,ciu_i,v_i,c_i,表示存在一条连接城市 uiu_i 和城市 viv_i 的双向道路,其费用为 cic_i。

接下来 qq 行,第 ii 行两个整数 ki,wik_i,w_i,表示一个新建道路的方案。

输出格式

共 qq 行,每行一个整数,第 ii 行的整数表示在新建一条连接城市 kik_i 和城市 n+1n+1 且费用为 wiw_i 的双向道路后,所有 cost(i,j)cost(i,j) 之和对 998244353998244353 取模的结果,即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$。

样例

4 2
2 1 3
3 2 2
4 2 4
1 2
2 2
100
88
9 5
2 3 6
6 1 4
5 2 10
2 4 1
9 1 9
2 8 3
1 2 3
7 4 8
4 9
7 3
6 1
9 7
2 1
1050
1054
970
1148
896

题目来源:洛谷 P9584