#P3498. PA2009 Cakes

    ID: 2710 传统题 3000ms 128MiB 尝试: 806 已通过: 139 难度: 6 上传者: 标签>CF1900提高三元环计数按度数定向时间戳避免清空数组杂项三元环

PA2009 Cakes

题目描述

给定一张包含 nn 个点和 mm 条边的无向图,顶点编号为 11 至 nn,每个点有一个点权 aia_i。图没有自环和重边。

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

求所有三元环的贡献和。

输入格式

第一行两个整数 n,mn,m,表示点的数量和边的数量。

第二行 nn 个正整数 aia_i,表示每个点的点权。

接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示一条无向边。

输出格式

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

样例输入

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)。 他们的贡献和为:5+5+4=145 + 5 + 4 = 14。

数据范围

2≤n≤1052\le n\le10^5,1≤m≤2.5×1051\le m\le2.5\times10^5。本站评测数据保证 1≤ai≤1061\le a_i\le10^6。