013 - ネットワークの課金システム

問題

それぞれ 0からN-1までの番号が割り当てられた N台のマシンが、合計 N-1本の双方向に通信できるケーブルで接続され、ネットワークを形成している。
どの２つのマシンも、いくつかのケーブルをたどって双方向に通信を行うことができる。
このネットワークでは、マシンが更新されると、通信量の増大に備えるために、そのマシンに直接接続されているすべてのケーブルをより太いものに交換する。

２つのマシンの間の通信料金は、その間を経由するすべてのケーブルの通信料金の総和になる。
ただし、このネットワークはユニークな課金システムで運営されており、太さが K の倍数であるようなケーブルは、そのケーブルの分の通信料金が無料になる。
それ以外のケーブルは、太さと同じ通信料金がかかる。

あなたの仕事は、このネットワークの料金計算システムを開発することである。

課題

ネットワークの形状とＱ個の命令が与えられたとき、それぞれの命令を処理するプログラムを作成せよ。
ただし、命令は以下の２種類である。

• マシン x に直接接続されている全てのケーブルの太さを d だけ増加させる。
• マシン s とマシン t の間の通信料金を報告する。

入力

入力は以下の形式で与えられる。

N K
a1 b1 c1
a2 b2 c2
:
aN-1 bN-1 cN-1
Q
query1
query2
:
queryQ

１行目に、マシンの総数N(2≦N≦10⁵)と、通信料金が無料になる太さを決める数K(1≦K≦10⁵)が与えられる。
続くN-1行に、２つのマシンを直接つなぐケーブルの情報が与えられる。
a_iとb_i(0≦a_i＜b_i≦N-1) はi番目のケーブルがつなぐ２つのマシンの番号を表し、c_i(1≦c_i≦10⁵)はそのケーブルの初期状態での太さを表す。
ただし、どの２つのマシンについても、それらを直接つなぐケーブルは１本以下とする。
続く１行に、命令の数Q(1≦Q≦10⁵)が与えられる。
続くQ行にi番目の命令query_iが与えられる。
各query_iは、以下のいずれかの形式で与えられる。

add x d

または

send s t

add x d は、マシンx(0≦x≦N-1)に直接接続されているすべてのケーブルの太さをd(1≦d≦10⁵)だけ増加させる。

send s t は、マシンs(0≦s≦N-1)とマシンt(0≦t≦N-1)の間の通信料金を報告する。
ただし、s≠tである。

入力には必ず１つ以上の send 命令が含まれる。

時間制限

入力に対して、実行時間が６秒を超えてはならない。

*実行時間制限が８秒になっていますが実際の問題は６秒です。
HOJでは実行時間制限６秒が選べないので8秒としています。

出力

各 send 命令について、マシンs とマシンt の間の通信料金を、それぞれ１行に出力する。

入出力例

入力例

6 3
0 1 1
0 2 1
0 3 1
2 4 1
2 5 1
3
send 1 4
add 2 2
send 1 4

出力例

3
1