問題
$1 \ $から$ \ N \ $までの番号がついた$ \ N \ $個の頂点を持つ根付き木が与えられます。この木の根は頂点$ \ 1 \ $で、$ \ i \ $番目の辺$ \ (1≤i≤N−1) \ $は頂点$ \ a_i \ $と頂点$ \ b_i \ $を結びます。
各頂点には重みというものが設定されており、はじめ全ての頂点の重みは$ \ 0 \ $です。
ここで、整数$ \ k \ (1 \leq k \leq N) \ $について関数$ \ f(k) \ $を以下のように定義します。
- $f(k):=$ 頂点$ \ k \ $を根とする部分木に含まれる全ての頂点の重みの総和。
以下のようなクエリが$ \ Q \ $回与えられるので順番に処理してください。また、各クエリの後に$ \ \sum_{k=1}^{N} f(k) \ $を$ \ 998244353 \ $で割った余りを求め出力してください。
x v: 頂点$ \ x \ $を根とする部分木に含まれるすべての頂点の重みに$ \ v \ $を加算する。
入力
入力は以下の形式で標準入力から与えられる。
$N \ Q$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_{N-1} \ b_{N-1}$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$
各クエリは以下の形式で与えられる。
$x \ v$
出力
$Q \ $行出力せよ。
$j \ (1 \leq j \leq Q) \ $行目には$ \ j \ $番目のクエリを処理した後の$ \ \sum_{k=1}^{N} f(k) \ $の値を$ \ 998244353 \ $で割った余りを出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,Q \leq 2 \times 10^5$
- $1 \leq a_i,b_i \leq N$
- $1 \leq x \leq N$
- $1 \leq v \leq 10^9$
- 与えられるグラフは木である
- 入力は全て整数である
入出力例
入力例1
4 2 1 2 2 3 2 4 3 2 1 3
出力例1
6 33
1つめのクエリでは、頂点$ \ 3 \ $に$ \ 2 \ $が加算され、それぞれの頂点の重みは$ \ \{0,0,2,0\} \ $となります。よって、$f(1) + f(2) + f(3) + f(4) = 2 + 2 + 2 + 0 = 6 \ $となります。
2つめのクエリでは、頂点$ \ 1,2,3,4 \ $に$ \ 3 \ $が加算され、それぞれの頂点の重みは$ \ \{3,3,5,3\} \ $となります。よって、$f(1) + f(2) + f(3) + f(4) = 14 + 11 + 5 + 3 = 33 \ $となります。
入力例2
10 10 3 1 7 8 7 5 2 4 7 10 4 3 7 9 2 7 2 6 2 647064727 8 914196209 10 464775783 9 82263895 6 731609037 6 444371053 6 165569768 9 335048863 1 362571412 7 518378247
出力例2
630595154 126306290 918472282 413811299 78879072 304245631 133850118 147654590 128887070 188190938
$998244353 \ $で割った余りを出力してください。