問題一覧 > 通常問題

No.1038 TreeAddQuery

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : ei1333333ei1333333 / テスター : beetbeet
3 ProblemId : 3912 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-04-24 15:55:41

問題文

$N$ 個の頂点と $N - 1$ 本の辺からなる木があります。 $i$ 番目の辺は頂点 $A_i, B_i$ を距離 $1$ で双方向に結んでいます。

最初, すべての頂点の重みは $0$ です。

$Q$ 個のクエリが時系列順に与えられるのですべて処理してください。$i$ 番目のクエリは以下を意味します。

  • 頂点 $X_i$ の現在の重みを出力し, 頂点 $X_i$ からの最短距離が $Y_i$ 以下であるすべての頂点(頂点 $X_i$ を含む)の重みに $Z_i$ を加算する

入力

$N$ $Q$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$:$
$A_{N-1}$ $B_{N-1}$
$X_{1}$ $Y_1$ $Z_1$
$X_{2}$ $Y_2$ $Z_2$
$:$
$X_{Q}$ $Y_Q$ $Z_Q$
  • $2 \leq N \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i, B_i \leq N$
  • $1 \leq X_i \leq N$
  • $0 \leq Y_i \leq N - 1$
  • $1 \leq Z_i \leq 10^9$
  • 入力はすべて整数
  • 与えられるグラフは木

出力

$Q$ 行からなります。$i$ 行目には $i$ 番目のクエリの時点での頂点 $X_i$ の重みを出力してください。

サンプル

サンプル1
入力
5 5
1 2
1 3
2 4
2 5
1 2 1
2 1 10
1 0 100
4 4 1000
5 1 10000
出力
0
1
11
11
1011
  • 最初, 頂点 $1, 2, 3, 4, 5$ の重みはそれぞれ $\{0, 0, 0, 0, 0\}$ です。
  • $1$ 番目のクエリでは頂点 $1$ からの最短距離が $2$ 以下である頂点 $1, 2, 3, 4, 5$ の重みに $1$ を加算します $\{\color{red}{1}, \color{red}{1}, \color{red}{1}, \color{red}{1}, \color{red}{1}\}$。
  • $2$ 番目のクエリでは頂点 $2$ からの最短距離が $1$ 以下である頂点 $1, 2, 4, 5$ の重みに $10$ を加算します $\{\color{red}{11}, \color{red}{11}, 1, \color{red}{11}, \color{red}{11}\}$。
  • $3$ 番目のクエリでは頂点 $1$ からの最短距離が $0$ 以下である頂点 $1$ の重みに $100$ を加算します $\{\color{red}{111}, 11, 1, 11, 11\}$。
  • $4$ 番目のクエリでは頂点 $4$ からの最短距離が $4$ 以下である頂点 $1, 2, 3, 4, 5$ の重みに $1000$ を加算します $\{\color{red}{1111}, \color{red}{1011}, \color{red}{1001}, \color{red}{1011}, \color{red}{1011}\}$。
  • $5$ 番目のクエリでは頂点 $5$ からの最短距離が $1$ 以下である頂点 $2, 5$ の重みに $10000$ を加算します $\{1111, \color{red}{11011}, 1001, 1011, \color{red}{11011}\}$。
サンプル2
入力
9 5
9 1
9 2
9 3
9 4
9 5
9 6
9 7
1 8
9 0 1
9 1 10
8 1 100
1 8 1000
2 4 10000
出力
0
1
0
110
1010
サンプル3
入力
2 4
1 2
1 1 1
2 1 2
1 0 3
2 0 4
出力
0
1
3
3

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