Charging System for Network

Time Limit : 3 sec, Memory Limit : 262144 KB

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

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

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

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

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

Input

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

N K
a_1 b_1 c_1
a_2 b_2 c_2
:
a_{N−1} b_{N−1} c_{N−1}
Q
query_1
query_2
:
query_Q

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

add x d

または

send s t

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

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

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

Output

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

Sample Input 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

Sample Output 1

3
1

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-9-9
http://web-ext.u-aizu.ac.jp/pc-concours/