24124번 - 高速道路 (Highway) 다국어

문제

カナダには,都市 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 へ の所要時間」を計算して答えなければならない.

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

입력

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

• 1 行目には整数 N と M が空白を区切りとして書かれている.
• 続く N − 1 行は,1 行につき 1 本の高速道路について記述している.これらの行の i 行目には 2 つの 整数 p_i, q_i (1 ≤ p_i < q_i ≤ N) が空白を区切りとして書かれており,これは高速道路 i が都市 p_i と都市 q_i を結んでいることを表す.
• 続く M 行は,1 行につき 1 つのクエリ (渋滞情報または問い合わせ) について記述しており.次のど ちらか一方が書いてある:
  • 渋滞情報 · · · 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).それぞれは空白 を区切りとして与えられる.

출력

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

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

제한

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

힌트