3074. 动物园

【题目描述】

  小 Z 计划带妹子去逛动物园。动物园有n个区域，从1到n编号。第i个区域有$a_i$只动物。动物园里有m条道路，道路是无向的，每条道路连接两个区域，且动物园是连通的，每两个区域之间都有路径相连。

  小 Z 为了哄妹子高兴，需要提前规划旅行路线。对于两个区域p和q(p ≠ q)间的任意一条简单路径，定义其高兴度为路径上经过的区域中最少的动物数量（包括区域p和区域q）。小 Z 自然希望高兴度越高越好，定义p、q(p ≠ q)间最大的高兴度为p 、 q间所有简单路径中高兴度的最大值，记作f(p,q)，现在小 Z 想知道，对于动物园任意两点的f(p,q)总和是多少。

【输入格式】

输入的第一行为两个整数n和m，第二行包含n个整数，表示每个区域动物的数量。

接下来的每行，每行包含两个数$x_i$和$y_i(x_i \neq y_i)$，表示区域$x_i$和$y_i$之间有一条道路。

【输出格式】

输出包含一行，一个整数表示最大高兴度总和，即$\sum_{p,q}^{p \neq q}{f(p,q)}$。

【样例输入】

4 5
40 20 30 40
1 2
2 3
1 3
2 4
3 4

【样例输出】

300

【提示】

f(1,2) = 20 f(1,3) = 30 f(1,4) = 30

f(2,1) = 20 f(2,3) = 20 f(2,4) = 20

f(3,1) = 30 f(3,2) = 20 f(3,4) = 30

f(4,1) = 30 f(4,2) = 20 f(4,3) = 30

综合为300

【数据规模与约定】

对于 10%的测试数据，满足2 ≤n≤ 10, n-1 ≤ m ≤ 20。

对于 30%的测试数据，满足2 ≤ n ≤ 200, n-1 ≤ m ≤ 1000。

对于 50%的测试数据，满足2 ≤ n ≤ 1000, n-1 ≤ m ≤ 20000。

对于 100%的测试数据，满足2 ≤ n ≤ 100000, n-1 ≤ m ≤ 1000000,

0 ≤$a_i$ ≤ 100000,1 ≤ $x_i, y_i$ ≤ ??,($x_i \neq y_i$)，保证是连通图且没有重边