AT_tkppc6_2_i 旅人計画問題2

有一张由 $n$ 个点（编号 $1$ 到 $n$）和 $n-1$ 条边（编号 $1$ 到 $n-1$）构成的无向图。第 $i$ 条边连接点 $u_i$ 和 $v_i$，边权为 $w_i$。初始时，$0 \le w_i \le 1$。 有一枚棋子将依次从 $x_0$ 点开始，依次访问 $x_1,x_2,...,x_m$ 这 $m$ 个点。中途可以经过其他点。 每次在移动时，可以使用与当前点有边直接相连的点移动，并将这条边的当前权值加入总权值中。之后，如果这条边的权值为 $p$，那么将其重新设为 $1-p$。 输入有 $q$ 次询问。内容如下： - `1 a b`：将 $x_a$ 更改为 $b$。 - `2 r`：请求出棋子从 $x_0$ 开始，依次访问 $x_1,x_2,...,x_r$ 所经过的边的最小总权值。此询问回答完毕后，将所有 $w$ 的值复原至初始状态。

第一行三个数 $n,m,q$。 第二行至第 $n$ 行，每行为一条边的信息 $u_i,v_i,w_i$。

按要求回答每个类型为 $2$ 的询问。每次回答完毕后都要换行。 ### 数据规模与约定 - $2 \le n \le 10^5$，$1 \le m,q \le 10^5$； - $1 \le u_i,v_i \le n$，$0 \le w_i \le 1$； - $1 \le x_i \le n$，$x_i \neq x_{i+1}$； - 对于任何一个询问 $1$，都有 $0 \le a \le m$，$1 \le b \le n$； - 对于任何一个询问 $2$，都有 $1 \le r \le m$； - 输入均为整数。

### 制約 - $ 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)