Highway(高速道路) - joi2010-day4

時間制限: 4秒

メモリ制限: 256MB

カナダには, 都市1から都市NまでのN個の都市と, 高速道路1から高速道路N-1までのN-1本の高速道路がある. すべての高速道路は2つの都市を結んでおり, どちらの方向にも通ることができる. さらにこの高速道路網は, どの2つの都市もいくつかの高速道路を乗り継ぐことで行き来できるように設計されている. 言い換えると, N個の都市とN-1本の高速道路は木構造をなしている.

渋滞情報センターの施設長に任命されたあなたは, この高速道路網の渋滞情報を管理しなければならない.

この施設では, N-1本それぞれの高速道路について, その始点の都市から終点の都市までの所要時間のデータを管理している. たとえば下図のように都市1と都市3, 都市3と都市4, 都市2と都市3が高速道路で繋がっている状況の場合, (i,j) = (1,3), (3,1), (3,4), (4,3), (2,3), (3,2) のそれぞれについて「都市iから都市jへの所要時間」をこの施設で管理している(高速道路は上りと下りで所要時間が同じとは限らないことに注意せよ).

それに加えて, この施設では次の2 つのことを行う.

まず, この施設には時おり「渋滞情報」が入ってくる. 1回の渋滞情報は3つの正の整数r,s,tによって与えられる. これは「高速道路rの上りの所要時間がs, 下りの所要時間がtである」ことを表す. ただし高速道路の上りとは, その高速道路の始点と終点の都市のうち番号が小さいほうの都市から大きいほうへの都市へと向かう方向を指し, 下りとはその逆方向を指すものとする. この渋滞情報に従って, 施設のデータを更新する.

また, この施設には「問い合わせ」の電話がかかってくることがある. 1回の問い合わせは2つの正の整数x,yによって与えられる.このとき, 施設で管理している現在のデータをもとに「都市xから都市yへの所要時間」を計算して答えなければならない.

課題(TASK)

ある1日の間の「渋滞情報」と「問い合わせ」(これらをまとめてクエリという)の列が時刻順に与えたとき, それぞれの問い合わせごとに, その問い合わせの答えを出力するプログラムを作成せよ. ただし, 最初の渋滞情報が入ってくる前の段階では, N-1本すべての高速道路の所要時間は上下線ともに1である.

制限(CONSTRAINTS)

2 ≤ N ≤ 100,000	都市の数
1 ≤ M ≤ 100,000	渋滞情報の数と問い合わせの数の和

入力(INPUT)

標準入力から以下の入力を読み込め.

1行目には整数NとMが空白を区切りとして書かれている.
続くN-1行は, 1行につき1本の高速道路について記述している. これらの行のi行目には2つの整数p[i],q[i] (1 ≤ pi < qi ≤ N) が空白を区切りとして書かれており, これは高速道路iが都市p[i]と都市q[i]を結んでいることを表す.
渋滞情報… 1文字 ‘I’ と, 整数r (1 ≤ r ≤ N-1), s (1 ≤ s ≤ 1,000), t (1 ≤ t ≤ 1,000). それぞれは空白を区切りとして与えられる.
問い合わせ… 1文字 ‘Q’ と, 異なる2つの整数x (1 ≤ x ≤ N), y (1 ≤ y ≤ N). それぞれは空白を区切りとして与えられる.

出力(OUTPUT)

標準出力に以下のデータを出力せよ.

出力するデータの行数は入力中に現れる文字 ‘Q’ の個数である. i行目は, 第i番目の問い合わせの答えを表す1つの整数を含む.

採点基準(GRADING)

20点分のテストグループにおいて, N,M は1,000を超えない. また, 50点分のテストグループにおいて, 任意の都市から別の任意の都市へ必ず1,000本以下の高速道路を乗り継いで移動することができる.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
`4 5 1 3 3 4 2 3 I 1 7 9 Q 2 4 I 3 12 11 Q 2 4 Q 4 2`	`2 13 12`