AT_tkppc6_2_i 旅人計画問題2

[problemUrl]: https://atcoder.jp/contests/tkppc6-2/tasks/tkppc6_2_i パ研王国は、$ 1 $ から $ N $ までの番号が振られた $ N $ 個の都市と、それらの間を結ぶ $ N-1 $ 本の道路からなります。$ i $ 本目の道路は都市 $ u_i $ と $ v_i $ を双方向に結び、また $ 0 $ 以上 $ 1 $ 以下の整数からなる重み $ w_i $ が割り当てられています。 さて、これからペンギンくんがパ研王国を旅します。ペンギンくんの旅は $ M+1 $ 個の整数 $ x_0,x_1,\ldots,x_M $ によって表され、これはペンギンくんが都市 $ x_0 $ から始めて都市 $ x_1,x_2,\ldots,x_M $ をこの順で訪れることを表します（途中で他の都市を経由してもよい）。 ペンギンくんは旅の最中、以下の行動を好きなだけ繰り返すことができます。 - 今いる都市と直接道路で結ばれている都市を $ 1 $ つ選び、道路を通ってその都市に移動する。コストに通った道路の重みが加算され、その後通った道路の重み（$ x $ とする）が $ 1-x $ に置き換わる。 ペンギンくんは旅全体を通じての合計コストを最小化したいです。 ところで、ペンギンくんはとても気まぐれです。そのため、以下のクエリを $ Q $ 個、与えられる順に処理してください。 - タイプ1: 整数 $ a,b $ が与えられる。$ x_a $ を $ b $ に変更する。 - タイプ2: 整数 $ r $ が与えられる。ペンギンくんが都市 $ x_0 $ から始めて $ x_1,x_2,\ldots,x_r $ をこの順に訪れるときの、合計コストの最小値を求める。なお、タイプ2のクエリは独立しているため、移動の最中における辺の重みの変更は次以降のクエリでは考慮しないものとする。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \hspace{0.8cm}\vdots $ $ u_{N-1} $ $ v_{N-1} $ $ w_{N-1} $ $ x_0 $ $ x_1 $ $ \ldots $ $ x_M $ $ \text{query}_1 $ $ \text{query}_2 $ $ \hspace{0.4cm}\vdots $ $ \text{query}_Q $ ここで $ \text{query}_i $ は $ i $ 個目のクエリの内容を表し、それぞれ以下の形式で与えられる。 - $ \text{type}=1 $ ならそのクエリがタイプ1であることを表し、入力のフォーマットは以下の通りである。 > $ \text{type} $ $ a $ $ b $ - $ \text{type}=2 $ ならそのクエリがタイプ2であることを表し、入力のフォーマットは以下の通りである。 > $ \text{type} $ $ r $

タイプ2のクエリが与えられるごとに問題文中で問われている値を出力し、改行せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ u_i,v_i\ \leq\ N\ (1\ \leq\ i\ \leq\ N-1) $ - $ 0\ \leq\ w_i\ \leq\ 1\ (1\ \leq\ i\ \leq\ N-1) $ - $ 1\ \leq\ x_i\ \leq\ N\ (0\ \leq\ i\ \leq\ M) $ - タイプ1のクエリにおいて、$ 0\ \leq\ a\ \leq\ M,1\ \leq\ b\ \leq\ N $ が成り立つ - タイプ2のクエリにおいて、$ 1\ \leq\ r\ \leq\ M $ が成り立つ - 各クエリの前後において、$ x_i\ \neq\ x_{i+1}\ (0\ \leq\ i\ \leq\ M-1) $ が成り立つ - $ Q $ 個目のクエリはタイプ2のクエリである - 与えられるグラフは木 - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 個目のクエリでは、ペンギンくんは頂点 $ 1 $ $ \rightarrow $ 頂点 $ 3 $ $ \rightarrow $ 頂点 $ 1 $ $ \rightarrow $ 頂点 $ 2 $ の順に移動するべきです。移動にかかるコストはそれぞれ $ 1 $, $ 0 $, $ 0 $ となるため、答えは $ 1 $ です。 $ 3 $ 個目のクエリでは、ペンギンくんは頂点 $ 1 $ $ \rightarrow $ 頂点 $ 3 $ $ \rightarrow $ 頂点 $ 1 $ $ \rightarrow $ 頂点 $ 3 $ の順に移動するべきです。移動にかかるコストはそれぞれ $ 1 $, $ 0 $, $ 1 $, $ 0 $ となるため、答えは $ 2 $ です。 ### Sample Explanation 2 原案: \[penguinman\](https://atcoder.jp/users/penguinman)