题目描述
给定两张都是 n 个点,m 条边的图 G1,G2,点有点权,设 ft(u,v) 表示第 t 张图,从 u 到 v 的所有简单路径中,权值最小的简单路径
一个简单路径的权值定义为经过的点的权值最小值
求:
1≤i<j≤n∑f1(i,j)×f2(i,j)
输入格式
第一行两个整数 n,m
之后一行 n 个整数,表示第一张图的点权 v1,1,v1,2,v1,3,⋯,v1,n
之后一共 m 行,每行两个整数 u,v,表示第一张图的 u,v 有一条无向边
之后一行 n 个整数,表示第二张图的点权 v2,1,v2,2,v2,3,⋯,v2,n
之后一共 m 行,每行两个整数 u,v,表示第二张图的 u,v 有一条无向边
输出格式
一行一个整数表示答案模 998244353 意义下的值
样例
5 4
6 6 6 8 2
2 1
3 2
4 3
5 2
1 4 4 3 9
2 1
3 2
4 1
5 1
62
数据范围与提示
保证两个图都是连通图,且 1≤n≤105,n−1≤m≤106,1≤v≤106
感谢 @liuzhangfeiabc 提供的测试点 6∼10