QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 4898. 基础图论练习题

统计

有一张 $n$ 个点的有边权无向图,结点按 $\{0, 1, \cdots, n - 1\}$ 编号。初始时有 $b$ 条边,第 $i$ 条连接 $u_i$ 和 $v_i$,边权为 $w_i$。

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

记最终得到的图为 $G$,其连通块依次为 $G_0, G_1, \cdots, G_{k-1}$。记 $f(G_i)$ 为 $G_i$ 的最小生成树大小(边权和),求 $\sum_{i=0}^{k-1} f(G_i)$。

答案对 $998244353$ 取模。

输入格式

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

接下来的 $a$ 行每行包含两个非负整数 $d_i, x_i(i = 1, 2, \cdots, a)$。

接下来的 $b$ 行每行包含三个非负整数 $u_i, v_i, w_i(i = 1, 2, \cdots, 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 \leq n \leq 10^{18}$,$0 \leq a, b \leq 5 \times 10^4$,$1 \leq d_i < n(1 \leq i \leq a)$,$0 \leq x_i < 998244353(1 \leq i \leq a)$,$0 \leq u_i, v_i < n, u_i \not= v_i(1 \leq i \leq b)$,$0 \leq w_i < 998244353(1 \leq i \leq b)$。

特殊限制 A:所有 $x_i$ 和 $w_i$ 均为 $1$。

subtask $1$($4$ pts):$n \leq 2 \times 10^5, a \leq 10$;

subtask $2$($8$ pts):$n \leq 2 \times 10^5$;

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

subtask $4$($18$ pts):$ a = 2, b \leq 5 \times 10^4$;

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

subtask $6$($12$ pts):$a \leq 1000, b \leq 200$;

subtask $7$($12$ pts):$b = 0$;

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

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

时间限制:$\texttt{3s}$

空间限制:$\texttt{512MB}$

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