#3498. [PA2009] Cakes

[PA2009] Cakes

题目描述

一个有 nn 个点 mm 条边的无向图,每个点有一个点权 aa

对于任意一个三元环 (i,j,k)(i,j,k)i<j<ki < j < k),它的贡献为 max(ai,aj,ak)\max (a_i,a_j,a_k)

求所有三元环的贡献和。

输入格式

1122 个整数 n,mn,m,表示点数和边数。

22nn 个整数 aia_i,表示每个点的点权。

33mm 行,每行 22 个整数 x,yx,y 表示一条边。

输出格式

一行一个整数,表示所有三元环的贡献和。

5 7
1 5 3 4 2
1 2
2 3
5 2
4 3
3 1
1 4
5 1
14

样例解释

三个三元环分别为:(1,2,3),(1,2,5),(1,3,4)(1,2,3),(1,2,5),(1,3,4)。他们的贡献和为 5+5+4=145 + 5 + 4 = 14

数据范围

对于所有数据,保证 1n1051 \leq n \leq 10^51m2.5×1051 \leq m \leq 2.5 \times 10^51ai1061\leq a_i \leq 10^61uivin1\leq u_i\neq v_i\leq n