#2022. 基础图论练习题

    ID: 2022 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest756来源:qoj.ac数据:公开样例最小生成树并查集

基础图论练习题

基础图论练习题

题目描述

标题: 基础图论练习题 - Problem - QOJ.ac

#4898. 基础图论练习题

Statistics

The problem was used in the following contests:

有一张 n 个点的有边权无向图,结点按 {0,1,⋯,n−1} 编号。初始时有 b 条边,第 i 条连接 ui 和 vi,边权为 wi。

接下来依次对它进行 a 次操作。第 i 次操作中,每对编号差为 di 的结点之间被连了一条权为 xi 的边。

记最终得到的图为 G,其连通块依次为 G0,G1,⋯,Gk−1。记 f(Gi) 为 Gi 的最小生成树大小(边权和),求 ∑i=0k−1f(Gi)。

答案对 998244353 取模。

输入格式

第一行包含三个非负整数 n,a,b。

接下来的 a 行每行包含两个非负整数 di,xi(i=1,2,⋯,a)。

接下来的 b 行每行包含三个非负整数 ui,vi,wi(i=1,2,⋯,b)。

输出格式

仅一行一个非负整数,表示答案模 998244353 后的余数。

样例一

input

13 2 3
4 16
5 17
10 2 3
0 7 19
5 6 12

output

177

样例二

input

80 5 10
35 5
68 7
4 11
67 15
21 18
1 20 13
33 48 5
37 68 16
64 72 4
22 11 13
73 17 1
24 71 9
71 30 9
16 18 2
13 2 4

output

512

样例三、样例四

见下发文件。

子任务

对于所有测试点:1≤n≤1018,0≤a,b≤5×104,1≤di<n(1≤i≤a),0≤xi<998244353(1≤i≤a),0≤ui,vi<n,ui≠vi(1≤i≤b),0≤wi<998244353(1≤i≤b)。

特殊限制 A:所有 xi 和 wi 均为 1。

subtask 1(4 pts):n≤2×105,a≤10;

subtask 2(8 pts):n≤2×105;

subtask 3(6 pts):a=2,b=0;

subtask 4(18 pts):a=2,b≤5×104;

subtask 5(12 pts):a≤1000,b=0,满足特殊限制 A;

subtask 6(12 pts):a≤1000,b≤200;

subtask 7(12 pts):b=0;

subtask 8(10 pts):满足特殊限制 A;

subtask 9(18 pts):无特殊限制。

时间限制:3s

空间限制:512MB

(注:出题人事后发现 subtask 5 和 8 的数据具有奇怪的的特殊性质,故这里建议选手自行尝试使用奇怪的程序通过 subtask 5 和 8。)

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

13 2 3
4 16
5 17
10 2 3
0 7 19
5 6 12
177

样例 2

80 5 10
35 5
68 7
4 11
67 15
21 18
1 20 13
33 48 5
37 68 16
64 72 4
22 11 13
73 17 1
24 71 9
71 30 9
16 18 2
13 2 4
512