← 返回题目列表

Codeforces · 2126/F

F. 1-1-1,免费树!

中文机器翻译题面 查看原题

给定一棵树$$$^{\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$$$。

输出

对于每个查询,在单独的行上输出一个整数 - 应用相应查询后树中所有边的成本之和。

示例

输入
复制

4
1 1
1
1 1
2 3
1 1
1 2 10
1 2
2 2
1 1
5 4
1 2 1 2 3
1 2 5
2 3 3
2 4 4
4 5 7
3 2
5 2
1 2
2 3
4 3
1 1 2 2
1 2 2
2 3 6
2 4 8
3 1
4 1
2 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$$$。