005 - RAQ on Tree

問題

$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 \ $で割った余りを出力してください。