#B. 切断公路

    Type: Default 1000ms 512MiB

切断公路

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

切断公路

题目背景

题目描述

小明在玩一款攻占城池的游戏,现在敌国拥有nn座城池,有n1n-1条公路将这些城池连接成一个整体,每个城市都有驻扎军队,第ii座城市的兵力为tit_i

小明注意到,城池之间会利用这些公路来运输粮草等补给,所以要攻占一座城就要切断这座城和其他城的连接。但是小明的野心很大,他想把这n1n-1条公路全部切断,准备一口气攻下这nn座城池。为了防止敌人重新打通这些公路,小明需要派遣足够的兵力去切断这些通路,需要的兵力至少是当前这条公路连接的两个连通块中,每个连通块的城池拥有的最大兵力之和。

小明有一个好消息和一个坏消息。坏消息是,已经派出去的兵力不能再次调动。好消息是,已经切断的公路不会重新被连通,因此他在切断某条公路之后,切断其他公路需要的兵力可能会更少。

小明意识到,不同的切割公路的顺序,所需要的总兵力不一定相同,所以他找到了你,想请你帮他计算,要切断所有n1n-1条公路,最少需要花费的总兵力是多少?

输入格式

第一行一个正整数nn表示城池数量。

第二行nn个正整数tit_i表示每个城池的兵力。

接下来n1n-1行每行两个正整数x,yx,y表示城池xxyy有公路连接。

输出格式

一个正整数表示小明需要派出的最小兵力。

样例 #1

样例输入 #1

3
1 2 3
1 2
2 3

样例输出 #1

8

提示

样例解释1:

先切断2到3的公路,此时城池被分成(1,2)和(3)两个连通块,第一个连通块的城池最大兵力是2,第二个连通块的城池最大兵力是3,所需兵力为2+3=5;再切断1到2的公路,将(1,2)分成(1)和(2)两个部分,所需兵力为1+2=3(因为城池3的兵力到不了这个连通块,所以不用管),因此所需的最小兵力总共是8。

如果先切断1到2的公路,此时城池被分成(1)和(2,3)两个连通块,第一个连通块的城池最大兵力是1,第二个连通块的城池最大兵力是3,所需兵力为1+3=4;再切断2到3的公路,所需兵力为2+3=5,总兵力为9,不是最小兵力。

数据范围

10%10\%的数据,n10n≤10

40%40\%的数据,n1000n≤1000

对另外10%10\%的数据,对任意1i<n1≤i<nii号点和i+1i+1号点相连。

100%100\%的数据,1n100000,1ti1091≤n≤100000,1≤t_i≤10^9

国庆集训S组模拟赛1

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2023-10-5 9:00
End at
2023-10-5 17:00
Duration
4 hour(s)
Host
Partic.
51