#P18452. Campus Partition

Campus Partition

Campus Partition

题目描述

Ham 是合肥著名的建筑师之一,受邀参与 USTC 新校区的规划。

校区是一棵有 nn 个建筑、n−1n-1 条无向边的树 T=(V,E)T=(V,E)。建筑 ii 的重要性为 wiw_i,保证整个校区连通。

学校希望把校区划分成若干个区域。一个划分合法,当且仅当:

  • 每个建筑恰好属于一个区域。
  • 每个区域所诱导的子图都连通。

区域的权值定义为其中所有建筑重要性的第二大值;只有一个建筑的区域权值为 00。第二大按建筑数量计数,相等的重要性也占据不同的位置。

请最大化所有区域的权值之和,并输出最大值。

若区域的建筑集合为 S⊆VS\subseteq V,其诱导子图包含 SS 中的所有建筑,以及原树中两端都属于 SS 的所有边。

输入格式

第一行包含正整数 nn,满足 1≤n≤5×1051\le n\le5\times10^5。

第二行包含 nn 个正整数 w1,w2,…,wnw_1,w_2,\ldots,w_n,满足 1≤wi≤1091\le w_i\le10^9。

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i,满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i,表示一条无向边。保证这些边构成一棵树。

输入只有一个实例,没有外层测试数据组数。建筑编号不保证与某个根下的父子顺序一致。

输出格式

输出一行一个整数,表示合法划分的最大区域权值之和。

原样例

8
2 5 4 5 3 1 1 3
1 2
1 3
1 4
2 5
2 6
3 7
4 8
8