問題一覧 > 通常問題

No.1637 Easy Tree Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 174
作問者 : harurunharurun / テスター : magstamagsta milkcoffeenmilkcoffeen
0 ProblemId : 6662 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-09 15:11:48

問題文

$1\sim N$ の番号が付いた $N$ 頂点の、頂点 $1$ を根とする木があります。

$i$ 番目の辺 $(1≤i≤N-1)$ は 頂点 $a_i$ と $b_i$ を結びます。

また、各頂点のコストは $0$ で初期化されています。

クエリが $Q$ 個与えられ、$j$ 個目のクエリでは以下の操作をします。クエリごとに木の全頂点のコストの総和を答えてください。

  • 頂点 $p_j$ を根とする部分木に含まれる全ての頂点のコストに $x_j$ を足す。 $(1≤j≤Q)$

制約

  • $2≤N≤10^5$

  • $1≤Q≤10^5$

  • $1≤a_i,b_i,p_j≤N$ $(1≤i≤N-1,1≤j≤Q)$

  • $1≤x_j≤10^8$ $(1≤j≤Q)$

  • 入力は全て整数である。

  • 与えられるグラフは木である。

入力

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$p_1$ $x_1$
$p_2$ $x_2$
$\vdots$
$p_Q$ $x_Q$
  • $1$ 行目に $N$ と $Q$ が空白区切りで与えられる。

  • $2$ 行目から $N$ 行目には、 $a_i$ と $b_i$ $(1≤i≤N-1)$ が空白区切りで与えられる。

  • $N+1$ 行目から $N+Q$ 行目には、 $p_j$ と $x_j$ $(1≤j≤Q)$ が空白区切りで与えられる。

出力

クエリごとの答えを $Q$ 行出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 1
1 2
1 3
1 5
出力
15

頂点 $1$ を根とする部分木に含まれる頂点は、 $(1,2,3)$ であり、それぞれのコストは $(0,0,0)$ です。それぞれに $5$ を足すと $(5,5,5)$ になり、総和は $15$ となります。

サンプル2
入力
10 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10
8 100
4 200
5 100
3 200
2 100
出力
200
1000
1100
1700
2300

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。