問題一覧 > 通常問題

No.1038 TreeAddQuery

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : ei1333333 / テスター : beet
お気に入りにしたユーザー ProblemId : 3912 / 自分の提出
問題文最終更新日: 2020-04-24 15:55:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 245 (順位表) の他の問題:

Problem Statement

There is a tree consisting of $N$ vertices and $N - 1$ edges. The $i$-th edge bidirectionally connects vertices $A_i, B_i$ with distance $1$.

Initially, the weights of all vertices are $0$.

You are given $Q$ queries in chronological order; process all of them. The $i$-th query means the following.

  • Output the current weight of vertex $X_i$, then add $Z_i$ to the weights of all vertices whose shortest distance from vertex $X_i$ is at most $Y_i$ (including vertex $X_i$).

Input

$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$
  • All inputs are integers.
  • The given graph is a tree.

Output

Output $Q$ lines. On the $i$-th line, output the weight of vertex $X_i$ at the time of the $i$-th query.

Sample

Sample 1
Input
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
Output
0
1
11
11
1011
  • Initially, the weights of vertices $1, 2, 3, 4, 5$ are $\{0, 0, 0, 0, 0\}$, respectively.
  • In query $1$, add $1$ to the weights of vertices $1, 2, 3, 4, 5$, whose shortest distance from vertex $1$ is at most $2$: $\{\color{red}{1}, \color{red}{1}, \color{red}{1}, \color{red}{1}, \color{red}{1}\}$.
  • In query $2$, add $10$ to the weights of vertices $1, 2, 4, 5$, whose shortest distance from vertex $2$ is at most $1$: $\{\color{red}{11}, \color{red}{11}, 1, \color{red}{11}, \color{red}{11}\}$.
  • In query $3$, add $100$ to the weight of vertex $1$, whose shortest distance from vertex $1$ is at most $0$: $\{\color{red}{111}, 11, 1, 11, 11\}$.
  • In query $4$, add $1000$ to the weights of vertices $1, 2, 3, 4, 5$, whose shortest distance from vertex $4$ is at most $4$: $\{\color{red}{1111}, \color{red}{1011}, \color{red}{1001}, \color{red}{1011}, \color{red}{1011}\}$.
  • In query $5$, add $10000$ to the weights of vertices $2, 5$, whose shortest distance from vertex $5$ is at most $1$: $\{1111, \color{red}{11011}, 1001, 1011, \color{red}{11011}\}$.
Sample 2
Input
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
Output
0
1
0
110
1010
Sample 3
Input
2 4
1 2
1 1 1
2 1 2
1 0 3
2 0 4
Output
0
1
3
3

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