4259: Bank Hacking
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：2
题目描述
C. Bank Hacking
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Although Inzane successfully found his beloved bone, Zane, his owner, has yet to return. To search for Zane, he would need a lot of money, of which he sadly has none. To deal with the problem, he has decided to hack the banks.
There are n banks, numbered from 1 to n. There are also n-1 wires connecting the banks. All banks are initially online. Each bank also has its initial strength: bank i has initial strength ai.
Let us define some keywords before we proceed. Bank i and bank j are neighboring if and only if there exists a wire directly connecting them. Bank i and bank j are semi-neighboring if and only if there exists an online bank k such that bank i and bank k are neighboring and bank k and bank j are neighboring.
When a bank is hacked, it becomes offline (and no longer online), and other banks that are neighboring or semi-neighboring to it have their strengths increased by 1.
To start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank x if and only if all these conditions are met:
There are n banks, numbered from 1 to n. There are also n-1 wires connecting the banks. All banks are initially online. Each bank also has its initial strength: bank i has initial strength ai.Let us define some keywords before we proceed. Bank i and bank j are neighboring if and only if there exists a wire directly connecting them. Bank i and bank j are semi-neighboring if and only if there exists an online bank k such that bank i and bank k are neighboring and bank k and bank j are neighboring.
When a bank is hacked, it becomes offline (and no longer online), and other banks that are neighboring or semi-neighboring to it have their strengths increased by 1.
To start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank x if and only if all these conditions are met:
- Bank x is online. That is, bank x is not hacked yet.
- Bank x is neighboring to some offline bank.
- The strength of bank x is less than or equal to the strength of Inzane's computer.
Input
The first line contains one integer n (1≤n≤3·105)− the total number of banks.The second line contains n integers a1,a2,...,an (-109≤ai≤109)− the strengths of the banks.
Each of the next n-1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi)− meaning that there is a wire directly connecting banks ui and vi.
It is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength.
Output
Print one integer− the minimum strength of the computer Inzane needs to accomplish the goal.
Examples
Input
5 1 2 3 4 5 1 2 2 3 3 4 4 5
Output
5
Input
7 38 -29 87 93 39 28 -55 1 2 2 5 3 2 2 4 1 7 7 6
Output
93
Input
5 1 2 7 6 7 1 5 5 3 3 4 2 4
Output
8
Note
In the first sample, Inzane can hack all banks using a computer with strength 5. Here is how:- Initially, strengths of the banks are [1,2,3,4,5].
- He hacks bank 5, then strengths of the banks become [1,2,4,5,-].
- He hacks bank 4, then strengths of the banks become [1,3,5,-,-].
- He hacks bank 3, then strengths of the banks become [2,4,-,-,-].
- He hacks bank 2, then strengths of the banks become [3,-,-,-,-].
- He completes his goal by hacking bank 1.
尽管Inzane成功地找到了他心爱的骨头，但他的主人Zane还没有回来。为了寻找赞恩，他需要很多钱，可惜他没有。为了解决这个问题，他决定入侵银行。
共有n个存储体，编号从1到n。还有n-1根电线连接存储体。所有银行最初都是在线的。每个银行也有其初始实力：银行i有初始实力ai。
让我们在继续之前定义一些关键字。存储体i和存储体j是相邻的，当且仅当存在直接连接它们的电线时。存储体i和存储体j是半相邻的，当且仅当存在在线存储体k。
当一家银行被黑客入侵时，它将离线（不再在线），与之相邻或半相邻的其他银行的实力将增加1。
为了开始他的计划，Inzane将首先选择一家银行进行黑客攻击。事实上，这家银行的实力绝不能超过他的电脑。在此之后，他将反复选择下一个要黑客攻击的银行，直到所有银行都被黑客攻击，但他可以继续黑客攻击x银行，前提是且仅当满足所有这些条件：
银行x在线。也就是说，x银行还没有被黑客入侵。
银行x与一些离线银行相邻。
银行x的强度小于或等于Inzane计算机的强度。
确定Inzane破解所有银行所需的计算机的最小强度。
输入格式
第一行包含一个整数n（1≤n≤3105）−存储体总数。
第二行包含n个整数a1，a2，。。。，an（-109≤ai≤109）-河岸的强度。
接下来的n-1行中的每一行包含两个整数ui和vi（1≤ui，vi≤n，ui≠vi）−意味着有一根电线直接连接组ui和vi。
可以保证，这些电线以这样的方式连接银行，即Inzane可以使用具有适当强度的计算机以某种方式破解所有银行。
第二行包含n个整数a1，a2，。。。，an（-109≤ai≤109）-河岸的强度。
接下来的n-1行中的每一行包含两个整数ui和vi（1≤ui，vi≤n，ui≠vi）−意味着有一根电线直接连接组ui和vi。
可以保证，这些电线以这样的方式连接银行，即Inzane可以使用具有适当强度的计算机以某种方式破解所有银行。
输出格式
打印一个整数，即Inzane完成目标所需的计算机的最小强度。
输入样例 复制
5
1 2 3 4 5
1 2
2 3
3 4
4 5输出样例 复制
5数据范围与提示
笔记
在第一个例子中，Inzane可以用一台5级的电脑破解所有银行。以下是方法：
最初，银行的优势是[1,2,3,4,5]。
他攻击了银行5，然后银行的实力变成了[1，2，4，5，-]。
他攻击了银行4，然后银行的实力变成[1,3,5，-，-]。
他攻击了银行3，然后银行的优势变成[2,4，-，-，-]。
他攻击了银行2，然后银行的优势变成了[3，-，-，-]。
他通过攻击1号银行完成了他的目标。
在第二个示例中，Inzane可以按顺序破解银行4、2、3、1、5、7和6。这样，他就可以用一台93级的电脑破解所有银行。
在第一个例子中，Inzane可以用一台5级的电脑破解所有银行。以下是方法：
最初，银行的优势是[1,2,3,4,5]。
他攻击了银行5，然后银行的实力变成了[1，2，4，5，-]。
他攻击了银行4，然后银行的实力变成[1,3,5，-，-]。
他攻击了银行3，然后银行的优势变成[2,4，-，-，-]。
他攻击了银行2，然后银行的优势变成了[3，-，-，-]。
他通过攻击1号银行完成了他的目标。
在第二个示例中，Inzane可以按顺序破解银行4、2、3、1、5、7和6。这样，他就可以用一台93级的电脑破解所有银行。