比赛场次 626
比赛名称 并查集专题
比赛状态 已结束比赛成绩
开始时间 2024-09-05 19:00:00
结束时间 2024-09-05 19:05:00
开放分组 全部用户
注释介绍 亲戚:模板题
食物链,银河英雄传说:带权并查集
oiwiki并查集应用:https://oi-wiki.org/topic/dsu-app/
动物园:A
树:D
呜呜呜 :E
Disruption:F
题目名称 动物园
输入输出 happyzoo.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分

动物园

★★   输入文件:happyzoo.in   输出文件:happyzoo.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

  小 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 ≤ 10^5, n-1 ≤ m ≤ 10^6,

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