問題文

Paken River では、技術室奥プログラミングコンテスト#5 の開催を記念し、このコンテストの末長い存続を願って、 灯籠流しが行われることになりました。
Paken River には $N$ 個の「チェックポイント」があり、$1$ から $N$ までの番号がつけられています。
チェックポイント $A_i$ と $B_i$ は、他のチェックポイントを経由せずに川でつながっており、この間を灯籠は時間 $C_i$ かけて流れます。
また、チェックポイント $1$ は、Paken River の河口であり、川はここへ向かって流れます。
さらに、すべてのチェックポイントは川を通してつながっており、 川が、流れる方向に向かって枝分かれすることはありません。
つまり、川は、チェックポイントを頂点とし、河口を根とした根付き木の形状をしています。
灯籠は、あるチェックポイントから流されると、川の流れに沿って進んでいき、流されてから、灯籠ごとに定められている時間が経つと消灯します。
最初の計画では、川にひとつも灯籠は流されません。次の $Q$ 個のクエリに答えてください。

• 追加クエリ: チェックポイント $v_i$ から時刻 $t_i$ に流す灯籠を追加する。この灯籠は $l_i$ 単位時間経つと消灯する。
• 回答クエリ: チェックポイント $v_i$ で時刻 $t_i$ までに点灯した状態で見られる灯籠の総数を出力する。ただし、時刻 $t_i$ ちょうどに見られる場合・$v_i$ から流す場合・$v_i$ に到達したときにちょうど消える場合(14:36 追記)も含める。このクエリでは必ず $l_i=0$ である。

入力

$N\ Q$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_{N-1}\ B_{N-1}\ C_{N-1}$
$type_1\ v_1\ t_1\ l_1$
$type_2\ v_2\ t_2\ l_2$
$\vdots$
$type_Q\ v_Q\ t_Q\ l_Q$

$type_i=0$ のとき追加クエリ、$type_i=1$ のとき回答クエリを表します。

• $2\leq N\leq 50000$
• $1\leq Q\leq 100000$
• $1\leq A_i,B_i,v_i\leq N$
• $0\leq C_i,t_i,l_i\leq 10^{12}$
• $type_i=0,1$
• $type_i=1$ なら $l_i=0$
• 与えられるグラフは木
• 入力は全て整数

出力

すべての回答クエリについて、チェックポイント $v_i$ で時刻 $t_i$ までに点灯した状態で見られる灯籠の総数をそれぞれ1行に出力してください。

小課題

実際に点数が与えられることはありませんが、この問題には、100点満点とした場合の複数の小課題が用意されています。
考察の助けや、コンテスト後の感想戦にご活用ください。なお、これらの制約を満たすテストケースの存在は保証されていません。(15:15 追記)

小課題1 (1点)

• $N,Q\leq 300$

小課題2 (15点)

• $C_i\leq 10^6$, $type_i=0$ なら $t_i\leq 10^6$, $type_i=1$ なら $t_i=10^{12}$

小課題3 (27点)

• $N,Q\leq 2000$

小課題4 (57点)

• 追加の制約はない。

サンプル

3 4
1 2 5
3 1 3
0 2 1 5
0 3 0 4
1 1 5 0
1 1 6 0

1
2

7 9
1 6 4
5 7 1
5 1 7
3 2 4
2 4 3
1 2 5
0 3 1 5
0 4 0 8
0 7 4 2
1 1 7 0
1 1 10 0
0 6 5 5
1 2 7 0
0 4 1 5
1 2 8 0

0
1
2
3