#P14869. [OOI2024 资格赛]Colorful graph彩色图

    ID: 14085 传统题 1500ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>CF2200图论并查集枚举数学队列动态规划

[OOI2024 资格赛]Colorful graph彩色图

题目描述

给定一张包含 nn 个顶点、mm 条边的无向图,边从 11 到 mm 编号。每条边被染成 kk 种颜色之一。第 ii 条边连接顶点 viv_i 和 uiu_i,颜色为 cic_i。

称一张图是好的,当且仅当可以在图中恰好保留 n−1n-1 条边,使得:

  • 保留下来的边构成一张连通图;
  • 每种颜色都至少有一条边被保留下来。

现在给出 qq 次边颜色修改。每次修改由两个数 ei,wie_i,w_i 描述,表示第 eie_i 条边的颜色变为 wiw_i。每次修改后,判断当前图是否是好的。

输入格式

第一行包含三个整数 n,m,kn,m,k(2≤n≤1000002 \le n \le 100000,1≤m≤1000001 \le m \le 100000,1≤k≤81 \le k \le 8),分别表示顶点数、边数和颜色数。

接下来 mm 行,每行包含三个整数 vi,ui,civ_i,u_i,c_i(1≤vi,ui≤n1 \le v_i,u_i \le n,1≤ci≤k1 \le c_i \le k,vi≠uiv_i \ne u_i),表示第 ii 条边的两个端点和颜色。

接下来一行包含一个整数 qq(1≤q≤1000001 \le q \le 100000),表示修改次数。

接下来 qq 行,每行包含两个整数 ei,wie_i,w_i(1≤ei≤m1 \le e_i \le m,1≤wi≤k1 \le w_i \le k),表示把第 eie_i 条边的颜色改为 wiw_i。

保证图中没有自环和重边。

输出格式

对于第 ii 次修改后的图,如果它是好的,输出 Yes;否则输出 No。

样例 #1

样例输入 #1

5 5 3
3 4 1
1 5 2
3 2 3
1 4 3
3 5 3
5
1 3
4 1
5 1
2 1
3 2

样例输出 #1

No
Yes
Yes
No
Yes

样例 #2

样例输入 #2

2 1 1
1 2 1
1
1 1

样例输出 #2

Yes

样例解释

第一个样例中,第一次修改后图如下。

此处应插入原题图:第一次修改后的彩色图。

此时没有颜色 11 的边,所以不可能满足题目条件。

第二次修改后图如下。

此处应插入原题图:第二次修改后的彩色图,原图中用红色标出了可以保留的边。

图中可以保留若干原题图中标红的边。这些边包含所有颜色 1,2,31,2,3,并且构成连通图,因此当前图是好的。

评分方式

测试数据包含 8 个测试组。只有通过该组以及若干指定的前置测试组,才能获得该组分数。Offline-testing 表示该组结果只会在比赛结束后公布。

组别 分数 附加限制 kk 依赖组 备注
0 - - 样例
1 10 k≤1k \le 1 -
2 9 k≤2k \le 2 1
3 15 k≤3k \le 3 0-2
4 16 k≤4k \le 4 0-3
5 14 k≤5k \le 5 0-4
6 13 k≤6k \le 6 0-5
7 12 k≤7k \le 7 0-6
8 11 k≤8k \le 8 0-7 Offline-testing