#P5750. [ZJOI2022] 简单题

    ID: 4751 传统题 6000ms 888MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS点双连通分量圆方树树链剖分LCA贡献法模逆元逆元线性递推

[ZJOI2022] 简单题

题目描述

九条可怜是一个喜欢出简单题的女孩子。顾名思义,简单题就是题目里面出现了很多 “简单”。

可怜首先给出一张简单连通无向图,每条边有一个正整数边权。特别地,可怜保证图上任意两个简单环的边权和相等。

后来可怜想要隐藏图里美好的性质,她将其中一部分边的权值改成了新的权值。因此,修改之后原本美好的性质可能就不存在了。

现在她给出修改后的图,同时给出多组询问,每次询问两点 S,TS, T 间所有简单路径权值和。因为答案可能很大,你只需要输出答案对 998244353998244353 取模的结果。

具体地,简单图指不存在重边和自环,简单环和简单路径指不包含重复节点。

输入格式

第一行读入三个整数 n,m,qn, m, q。

接下来 mm 行,每行三个整数 u,v,wu, v, w,代表一条权值为 ww 的无向边 (u,v)(u, v)。

接下来 qq 行,读入 qq 组询问,每组询问读入一行两个整数 S,TS, T。

输出格式

对于每个询问,输出一行一个整数代表答案对 998244353998244353 取模后的结果。

样例 #1

样例输入 #1

5 5 6
1 2 10
2 3 2
2 4 5
2 5 4
4 5 3
1 5
2 5
3 5
3 4
4 5
4 4

样例输出 #1

32
12
16
16
12
0

样例 #2

样例输入 #2

见附件中的 simple/simple_ex2.in

样例输出 #2

见附件中的 simple/simple_ex2.ans

提示

对于所有测试点,满足 1≤n,q≤5×1051 \le n, q \le 5 \times {10}^5,n−1≤m≤6.4×105n - 1 \le m \le 6.4 \times {10}^5,1≤u,v,S,T≤n1 \le u, v, S, T \le n,1≤w≤1061 \le w \le {10}^6,无重边自环,图连通。

每个测试点的具体限制见下表:

测试点编号 特殊限制 1 特殊限制 2
11 m<nm < n 保证存在经过所有点的简单路径
22 无
3∼53 \sim 5 任意一个点不在 ≥2\ge 2 个简单环上 保证存在经过所有点的简单路径
6∼86 \sim 8 无
9∼149 \sim 14 无 保证存在经过所有点的简单路径
15∼2015 \sim 20 无