P9584 "MXOI Round 1" City

Little C is the president of Country F. Although this country exists only in an online game, he is indeed the president of this country. Country F consists of $n$ cities. These $n$ cities are connected by $n-1$ bidirectional roads. It is guaranteed that starting from any city, you can reach any other city through these $n-1$ bidirectional roads. Of course, using these bidirectional roads costs money. Passing through the $i$-th bidirectional road costs $c_i$ yuan. We call $c_i$ the cost of the $i$-th bidirectional road. We define $cost(x,y)$ as the sum of the costs of all bidirectional roads on the simple path from city $x$ to city $y$. In particular, when $x=y$, $cost(x,y)=0$. To promote the development of Country F, Little C built a new city $n+1$. Now he needs to build one more bidirectional road so that city $n+1$ can also reach any city through these $n$ bidirectional roads. He has a total of $q$ road-building plans. Each plan provides two parameters $k_i,w_i$. For each plan, you need to compute, after building a bidirectional road connecting city $k_i$ and city $n+1$ with cost $w_i$, the sum of all $cost(i,j)$, i.e. $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$. Since the answer may be very large, you only need to output the result modulo $998244353$. **The plans are independent of each other**, meaning none of the plans will affect the existing roads, and these plans will not actually be carried out.

The first line contains two integers $n,q$. The next $n-1$ lines: the $i$-th line contains three integers $u_i,v_i,c_i$, indicating that there is a bidirectional road connecting city $u_i$ and city $v_i$ with cost $c_i$. The next $q$ lines: the $i$-th line contains two integers $k_i,w_i$, indicating a plan for building a new road.

Output $q$ lines, each containing one integer. The integer on the $i$-th line denotes, after building a bidirectional road connecting city $k_i$ and city $n+1$ with cost $w_i$, the sum of all $cost(i,j)$ modulo $998244353$, i.e. $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$.

#### Sample Explanation #1 After building a bidirectional road connecting city $1$ and city $5$ with cost $2$, the roads of Country F are as shown in the figure below:  For example, in this case, $cost(4,5)=9$ and $cost(1,3)=5$. It is easy to obtain that $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$. #### Sample #3 See `city/city3.in` and `city/city3.ans` in the additional files. This sample satisfies the constraints of test point $4$. #### Sample #4 See `city/city4.in` and `city/city4.ans` in the additional files. This sample satisfies the constraints of test point $11$. #### Sample #5 See `city/city5.in` and `city/city5.ans` in the additional files. This sample satisfies the constraints of test point $14$. #### Sample #6 See `city/city6.in` and `city/city6.ans` in the additional files. This sample satisfies the constraints of test point $20$. #### Constraints For $100\%$ of the data, $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$. It is guaranteed that starting from any city, you can reach any other city through the original $n-1$ bidirectional roads. |Test Point ID|$n \le$|$q \le$|Special Property| |:---:|:---:|:---:|:---:| |$1\sim3$|$80$|$80$|None| |$4\sim7$|$5000$|$5000$|None| |$8\sim10$|$5000$|$2\times10^5$|None| |$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$|None| Special Property A: It is guaranteed that for all $1 \le i \lt n$, $u_i=i,v_i=i+1$. Special Property B: It is guaranteed that for all $1 \le i \le q$, $k_i=1$. Translated by ChatGPT 5