QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+25]

# 4898. 基础图论练习题

Statistics

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

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

记最终得到的图为 G,其连通块依次为 G0,G1,,Gk1。记 f(Gi)Gi 的最小生成树大小(边权和),求 k1i=0f(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

样例三、样例四

见下发文件。

子任务

对于所有测试点:1n10180a,b5×1041di<n(1ia)0xi<998244353(1ia)0ui,vi<n,uivi(1ib)0wi<998244353(1ib)

特殊限制 A:所有 xiwi 均为 1

subtask 1(4 pts):n2×105,a10

subtask 2(8 pts):n2×105

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

subtask 4(18 pts):a=2,b5×104

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

subtask 6(12 pts):a1000,b200;

subtask 7(12 pts):b=0

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

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

时间限制:3s

空间限制:512MB

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