#P10493. [2021年联测]lotsofvaluableenergy
[2021年联测]lotsofvaluableenergy
题目描述
给定一棵有 个点的树,以及一个长度为 的整数序列 。
任选一个点,先将它加入集合。接下来进行 次操作。每次选择一个尚未加入集合、且有相邻点已经在集合中的点,把它加入集合,并把它与集合中相邻点之间的边权设为 ,其中 是当前操作的编号。由于原图是树且集合一直连通,每次只有一个这样的相邻点。
你可以决定起点和操作顺序。求能够得到的最大树直径,即所有路径中最大边权和的最大可能值。
输入格式
第一行一个整数 。第二行 个整数 。
接下来 行,每行两个整数 ,表示树的一条边。点编号为 到 。
输出格式
一行一个整数,表示可以得到的最大树直径。
样例
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
16
数据范围
,。现有评测输入的 均为正整数。
| 原赛子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | 20 | |
| 2 | 25 | |
| 3 | ,第 条边满足 且 | 10 |
| 4 | ,所有 | 15 |
| 5 | 20 | |
| 6 | 10 |