/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
パ研王国は、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のクエリは独立しているため、移動の最中における辺の重みの変更は次以降のクエリでは考慮しないものとする。
制約
- 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のクエリである
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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のクエリが与えられるごとに問題文中で問われている値を出力し、改行せよ。
入力例 1
3 3 3 1 2 0 1 3 1 1 3 2 3 2 2 1 2 1 2 3
出力例 1
1 2
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 です。
入力例 2
5 10 8 1 2 0 3 1 0 2 4 0 5 4 1 1 3 4 2 5 3 1 3 4 2 4 1 2 1 1 6 2 2 5 1 6 4 2 9 2 8 1 7 1 2 2
出力例 2
4 9 8 1
原案: penguinman