問題一覧 > 通常問題

No.1197 モンスターショー

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 17
作問者 : ThistleThistle / テスター : definedefine
0 ProblemId : 4862 / 出題時の順位表
問題文最終更新日: 2020-08-22 11:30:48

問題文

$1, 2, \dots, N$ と番号の振られた $N$ 個の町があり、$N-1$ 本の道でつながれています。
$i$ 番目の道は町 $A_i$ と町 $B_i$ をつないでいて、長さは $1$ です。どの町からでも何本かの道を通ることで他すべての町に行くことができます。
分かりやすく言えば、全ての町と道は木構造になっています。

パ研君は $K$ 匹のスライムを飼っていて、$i(1\leq i\leq K)$ 番目のスライムは最初町 $C_i$ にいます。
スライムは町を移動することがあります。

町を移動しながらモンスターショーを行うパ研君は、ある時にスライムをすべて彼のいる町に呼び寄せたときの、 スライムの移動距離の総和が知りたいです。

パ研君はこれを求めようとしましたが、とても難しかったので、高名な競技プログラマーであるあなたに依頼をすることにしました。

パ研君からの依頼内容は、$Q$ 個のクエリを処理することです。クエリは 2 種類あり、以下の形式で与えられます。

  • 1 p d : $p$ 番目のスライムが町 $d$ に移動した。
  • 2 e : 町 $e$ にスライムをすべて集めるときのスライムの移動距離の総和を求め、出力する。
  • 入力

    $N\ K\ Q$
    $C_1\ C_2 \dots C_K$
    $A_1\ B_1$
    $A_2\ B_2$
    $\dots$
    $A_{N-1}\ B_{N-1}$
    $Query_1$
    $Query_2$
    $\dots$
    $Query_Q$
    

  • $1\leq N,K,Q\leq 10^5$
  • $1\leq C_i\leq\ N\ (1\leq i\leq K)$
  • $1\leq A_i, B_i\leq\ N\ (1\leq i\leq N-1)$
  • $1\leq p\leq K$
  • $1\leq d,e\leq N$
  • 入力は全て整数。
  • 入力で与えられるグラフは木である。
  • 出力

    2 種類目のクエリが与えられたとき、移動距離の総和を 1 行に出力し改行してください。

    サンプル

    サンプル1
    入力
    3 2 2
    1 3
    2 1
    3 1
    2 3
    2 2
    
    出力
    1
    3
    

    最初のクエリでは、町 3 に 2 匹のスライムを呼び寄せます。
    町 3 と町 1 、町 3 と町 3 の距離はそれぞれ $1,0$ なので、$1+0=1$ を出力します。
    次のクエリでは、町 2 にスライムを呼び寄せます。距離の総和は $3$ となるので、$3$ を出力します。

    サンプル2
    入力
    4 2 3
    4 3
    2 1
    3 1
    4 2
    2 2
    1 2 1
    2 1
    
    出力
    3
    2
    

    最初のクエリでは、スライムは町 4 と町 3 の 2 か所にいます。このそれぞれから、町 2 へ向かう距離の和を計算すると $3$ となるので、$3$ を出力します。
    次のクエリでは、スライム 2 が町 3 から町 1 に移動します。
    最後のクエリでは、スライムが町 4 と町 1 の 2 か所にいて、このそれぞれから町 1 へ向かう距離の和を計算すると $2$ となるので、$2$ を出力します。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。