题目详情题解（0）讨论（0）提交记录（0）

CF2126F.1-1-1, Free Tree!

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵有 nn 个顶点的树（编号为 11 到 nn）。每个顶点有一个初始颜色 aia_i。

树的每条边由三个数 uiu_i、viv_i 和 cic_i 定义，其中 uiu_i 和 viv_i 是边的两个端点，cic_i 是该边的参数。边的代价定义如下：如果顶点 uiu_i 和 viv_i 的颜色相同，则代价为 00；否则代价为 cic_i。

你还会得到 qq 个操作。每个操作的形式为：将顶点 vv 重新染成颜色 xx。这些操作是依次进行的（每次操作后的颜色变化会保留到下一次操作）。每次操作后，你需要输出当前树中所有边的总代价之和。

一棵树是一个无环连通图。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。

每个测试用例的第一行包含两个整数 nn 和 qq（1≤n,q≤2⋅1051 \le n, q \le 2\cdot10^5），分别表示顶点数和操作数。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（1≤ai≤n1 \le a_i \le n），表示每个顶点的初始颜色。

接下来的 n−1n-1 行，每行三个整数 uu、vv、cc，表示一条连接顶点 uu 和 vv 的边，参数为 cc（1≤u,v≤n1 \le u, v \le n，1≤c≤1091 \le c \le 10^9）。

接下来的 qq 行，每行两个整数 vv 和 xx，表示将顶点 vv 重新染成颜色 xx（1≤v,x≤n1 \le v, x \le n）。

保证所有测试用例中 nn 的总和和 qq 的总和不超过 2⋅1052\cdot10^5。

输出格式

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

输入输出样例

  • 输入#1

    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

    输出#1

    0
10
0
10
12
5
0
12
8
0
16

说明/提示

第一组样例：n=1n=1，只有一个顶点，没有边。操作：将 a1a_1 染成 11，总代价为 00。

第二组样例：n=2n=2，边 1−21-2（c=10c=10）。操作如下：

  • a1=2a_1=2：颜色为 [2,1][2,1]，总代价为 1010；
  • a2=2a_2=2：颜色为 [2,2][2,2]，总代价为 00；
  • a1=1a_1=1：颜色为 [1,2][1,2]，总代价为 1010。

第三组样例：n=5n=5，边为：1−2 (c=5)1-2\ (c=5)，2−3 (c=3)2-3\ (c=3)，2−4 (c=4)2-4\ (c=4)，4−5 (c=7)4-5\ (c=7)。初始颜色 [1,2,1,2,3][1,2,1,2,3]。操作如下：

a3=2→[1,2,2,2,3]a_3=2 \rightarrow [1,2,2,2,3]：边 1−2 (c=5)1-2\ (c=5) 和 4−5 (c=7)4-5\ (c=7) 贡献总代价 1212；

a5=2→[1,2,2,2,2]a_5=2 \rightarrow [1,2,2,2,2]：边 1−2 (c=5)1-2\ (c=5)，总代价 55；

a1=2→[2,2,2,2,2]a_1=2 \rightarrow [2,2,2,2,2]：总代价为 00；

a2=3→[2,3,2,2,2]a_2=3 \rightarrow [2,3,2,2,2]：边 1−2 (5)1-2\ (5)，2−3 (3)2-3\ (3)，2−4 (4)2-4\ (4) 贡献总代价 1212。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页