CF2126F 1-1-1, Free Tree!

给定一棵有 $n$ 个顶点的树（编号为 $1$ 到 $n$）。每个顶点有一个初始颜色 $a_i$。 树的每条边由三个数 $u_i$、$v_i$ 和 $c_i$ 定义，其中 $u_i$ 和 $v_i$ 是边的两个端点，$c_i$ 是该边的参数。边的代价定义如下：如果顶点 $u_i$ 和 $v_i$ 的颜色相同，则代价为 $0$；否则代价为 $c_i$。 你还会得到 $q$ 个操作。每个操作的形式为：将顶点 $v$ 重新染成颜色 $x$。这些操作是依次进行的（每次操作后的颜色变化会保留到下一次操作）。每次操作后，你需要输出当前树中所有边的总代价之和。 一棵树是一个无环连通图。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2\cdot10^5$），分别表示顶点数和操作数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示每个顶点的初始颜色。 接下来的 $n-1$ 行，每行三个整数 $u$、$v$、$c$，表示一条连接顶点 $u$ 和 $v$ 的边，参数为 $c$（$1 \le u, v \le n$，$1 \le c \le 10^9$）。 接下来的 $q$ 行，每行两个整数 $v$ 和 $x$，表示将顶点 $v$ 重新染成颜色 $x$（$1 \le v, x \le n$）。 保证所有测试用例中 $n$ 的总和和 $q$ 的总和不超过 $2\cdot10^5$。

对于每个操作，输出一个整数，表示执行该操作后树中所有边的总代价。每个答案占一行。

第一组样例：$n=1$，只有一个顶点，没有边。操作：将 $a_1$ 染成 $1$，总代价为 $0$。 第二组样例：$n=2$，边 $1-2$（$c=10$）。操作如下： - $a_1=2$：颜色为 $[2,1]$，总代价为 $10$； - $a_2=2$：颜色为 $[2,2]$，总代价为 $0$； - $a_1=1$：颜色为 $[1,2]$，总代价为 $10$。 第三组样例：$n=5$，边为：$1-2\ (c=5)$，$2-3\ (c=3)$，$2-4\ (c=4)$，$4-5\ (c=7)$。初始颜色 $[1,2,1,2,3]$。操作如下： $a_3=2 \rightarrow [1,2,2,2,3]$：边 $1-2\ (c=5)$ 和 $4-5\ (c=7)$ 贡献总代价 $12$； $a_5=2 \rightarrow [1,2,2,2,2]$：边 $1-2\ (c=5)$，总代价 $5$； $a_1=2 \rightarrow [2,2,2,2,2]$：总代价为 $0$； $a_2=3 \rightarrow [2,3,2,2,2]$：边 $1-2\ (5)$，$2-3\ (3)$，$2-4\ (4)$ 贡献总代价 $12$。 由 ChatGPT 4.1 翻译