给定一棵树$$$^{\text{*}}$$$,其$$$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$$$。查询相互依赖(每次查询后,颜色变化都会被保留)。每次查询后,您需要输出树中所有边的成本之和。
$$$^{\text{*}}$$$树是没有环的连通图。
输入
第一行包含一个整数 $$$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$$$),其中第 $$$i$$$ 数字指定顶点 $$$i$$$ 的初始颜色。
接下来的 $$$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$$$。
输出
对于每个查询,在单独的行上输出一个整数 - 应用相应查询后树中所有边的成本之和。
示例
输入复制
41 111 12 31 11 2 101 22 21 15 41 2 1 2 31 2 52 3 32 4 44 5 73 25 21 22 34 31 1 2 21 2 22 3 62 4 83 14 12 2
输出复制
0 10 0 10 12 5 0 12 8 0 16
注意
第一个测试:$$$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$$$。