#P10493. [2021年联测]lotsofvaluableenergy

    ID: 9610 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DP逆向思考滚动数组深度优先搜索

[2021年联测]lotsofvaluableenergy

题目描述

给定一棵有 n+1n+1 个点的树,以及一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n。

任选一个点,先将它加入集合。接下来进行 nn 次操作。每次选择一个尚未加入集合、且有相邻点已经在集合中的点,把它加入集合,并把它与集合中相邻点之间的边权设为 aia_i,其中 ii 是当前操作的编号。由于原图是树且集合一直连通,每次只有一个这样的相邻点。

你可以决定起点和操作顺序。求能够得到的最大树直径,即所有路径中最大边权和的最大可能值。

输入格式

第一行一个整数 nn。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 nn 行,每行两个整数 ui,viu_i,v_i,表示树的一条边。点编号为 11 到 n+1n+1。

输出格式

一行一个整数,表示可以得到的最大树直径。

样例

5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
16

数据范围

n≤150n\le150,ai≤109a_i\le10^9。现有评测输入的 aia_i 均为正整数。

原赛子任务 特殊限制 原赛分值
1 n≤8n\le8 20
2 n≤15n\le15 25
3 n≤15n\le15,第 ii 条边满足 ui=iu_i=i 且 vi=i+1v_i=i+1 10
4 n≤15n\le15,所有 ui=1u_i=1 15
5 n≤80n\le80 20
6 n≤150n\le150 10

原 PDF 题面