#PQJ921x4009. QOJ 921_4009
QOJ 921_4009
ZJOI 2022 第一试 简单题(simple) 简单题(simple) 【题目描述】 九条可怜是一个喜欢出简单题的女孩子。顾名思义,简单题就是题目里面出现了很多“简单”。 可怜首先给出一张简单连通无向图,每条边有一个正整数边权。特别地,可怜保证图上任意两个 简单环的边权和相等。 后来可怜想要隐藏图里美好的性质,她将其中一部分边的权值改成了新的权值。因此,修改之后 原本美好的性质可能就不存在了。 现在她给出修改后的图,同时给出多组询问,每次询问两点S, T 间所有简单路径权值和。因为 答案可能很大,你只需要输出答案对998 244 353 取模的结果。 具体地,简单图指不存在重边和自环,简单环和简单路径指不包含重复节点。 【输入格式】 从文件simple.in 中读入数据。 第一行读入三个整数n, m, q。 接下来m 行,每行三个整数u, v, w,代表一条权值为w 的无向边(u, v)。 接下来q 行,读入q 组询问,每组询问读入一行两个整数S, T。 【输出格式】 输出到文件simple.out 中。 对于每个询问,输出一行一个整数代表答案对998 244 353 取模后的结果。 【样例输入】 见下发文件中的simple ex1.in和simple ex2.in。 【样例输出】 见下发文件中的simple ex1.ans和simple ex2.ans。 第6 页 共7 页
ZJOI 2022 第一试 简单题(simple) 【数据范围与提示】 对于所有测试点,满足1 ≤n, q ≤500 000 ,n −1 ≤m ≤640 000 ,1 ≤u, v, S, T ≤n , 1 ≤w ≤106,无重边自环,图连通。 每个测试点的具体限制见下表: 测试点编号 特殊限制1 特殊限制2 1 m < n 保证存在经过所有点的简单路径 2 m < n 无 3 ∼5 任意一个点不在≥2 个简单环上 保证存在经过所有点的简单路径 6 ∼8 任意一个点不在≥2 个简单环上 无 9 ∼14 无 保证存在经过所有点的简单路径 15 ∼20 无 无 第7 页 共7 页