#P18452. Campus Partition
Campus Partition
Campus Partition
题目描述
Ham 是合肥著名的建筑师之一,受邀参与 USTC 新校区的规划。
校区是一棵有 个建筑、 条无向边的树 。建筑 的重要性为 ,保证整个校区连通。
学校希望把校区划分成若干个区域。一个划分合法,当且仅当:
- 每个建筑恰好属于一个区域。
- 每个区域所诱导的子图都连通。
区域的权值定义为其中所有建筑重要性的第二大值;只有一个建筑的区域权值为 。第二大按建筑数量计数,相等的重要性也占据不同的位置。
请最大化所有区域的权值之和,并输出最大值。
若区域的建筑集合为 ,其诱导子图包含 中的所有建筑,以及原树中两端都属于 的所有边。
输入格式
第一行包含正整数 ,满足 。
第二行包含 个正整数 ,满足 。
接下来 行,每行包含两个整数 ,满足 、,表示一条无向边。保证这些边构成一棵树。
输入只有一个实例,没有外层测试数据组数。建筑编号不保证与某个根下的父子顺序一致。
输出格式
输出一行一个整数,表示合法划分的最大区域权值之和。
原样例
8
2 5 4 5 3 1 1 3
1 2
1 3
1 4
2 5
2 6
3 7
4 8
8