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

時間制限 4 秒 / メモリ制限 64 MB / 得点 11 / x 0 /


TLE
4sec
MLE
64MB
得点
11

問題

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

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

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

課題

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

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

入力

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

N K
a1 b1 c1
a2 b2 c2
:
aN-1 bN-1 cN-1
Q
query1
query2
:
queryQ
1行目に、マシンの総数N(2≦N≦105)と、通信料金が無料になる太さを決める数K(1≦K≦105)が与えられる。
続くN-1行に、2つのマシンを直接つなぐケーブルの情報が与えられる。
aiとbi(0≦ai<bi≦N-1) はi番目のケーブルがつなぐ2つのマシンの番号を表し、ci(1≦ci≦105)はそのケーブルの初期状態での太さを表す。
ただし、どの2つのマシンについても、それらを直接つなぐケーブルは1本以下とする。
続く1行に、命令の数Q(1≦Q≦105)が与えられる。
続くQ行にi番目の命令queryiが与えられる。
各queryiは、以下のいずれかの形式で与えられる。
add x d
または
send s t

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

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

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

時間制限

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

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

出力

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

入出力例

入力例

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