Bank Hacking
Contest: Codeforces Round 408 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, dp, trees

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:

1. Bank x is online. That is, bank x is not hacked yet.
2. Bank x is neighboring to some offline bank.
3. The strength of bank x is less than or equal to the strength of Inzane's computer.

Determine the minimum strength of the computer Inzane needs to hack all the banks.

Input format:
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 format:
Print one integer — the minimum strength of the computer Inzane needs to accomplish the goal.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

In the second sample, Inzane can hack banks 4, 2, 3, 1, 5, 7, and 6, in this order. This way, he can hack all banks using a computer with strength 93.

Example input:
5
1 2 3 4 5
1 2
2 3
3 4
4 5

Example output:
5

Example input:
7
38 -29 87 93 39 28 -55
1 2
2 5
3 2
2 4
1 7
7 6

Example output:
93

Editorial:
First, note that the input graph is a tree.
Let m be the greatest value of ai (that is, max(a1, a2, ..., an)). Observe that the answer can be m, m + 1, or m + 2 only.
Why? It is because each bank’s strength can be increased at most twice, once by a neighboring bank, and once by a semi-neighboring bank. So the strength required to hack bank i is at most ai + 2, regardless of the sequence of banks you choose to hack.
Now, suppose u is the first bank we would hack first. We would need a computer with strength at least au to hack it. Let the neighboring banks of u be v1, v2, ..., vk. We would need a computer with strength at least avi + 1 to hack those banks. And for each bank x not yet hacked, we can hack them with a computer with strength at least ax + 2.
For simplicity, add 2 to all the banks’ strengths. Let’s maintain a map data structure to keep track of number of times some value of strength occurs. Again, suppose we would start by hacking bank u. Now, we would need a computer with strength at least au - 2 to hack it. For the neighboring banks v, it would be av - 1. For other banks x, it would be ax.
For a fixed bank u, you can iterate through its neighboring banks, and update the map data structure accordingly. Keep track of the maximum value that occurs, and update the answer.
We can simply iterate through banks u to start with, and get the final answer.
But wait. Won’t it work in $$O(n^2 \log n)$$ or something like that?
No. Let’s analyze the runtime carefully. (You can skip this if you know why. This is for beginners.)
Suppose we choose bank u to start with. We have to iterate through its neighboring banks. The number of the banks neighboring to u is equal to the degree of bank u. We would need O(1 + du) operations for bank u.
By iterating through all possible u from 1 to n, we will perform O(n + d1 + d2 + ... + dn) operations. You can see that if there are m edges in a graph, the degrees of all nodes sum to 2m. Trees have n - 1 edges, so d1 + d2 + ... + dn  =  2(n - 1)  =  2n - 2  =  O(n). Therefore, we need to perform only O(n) operations. However, each operation involves the map data structure, so the overall runtime is $$O(n \log n)$$. Be aware that the use of hash map could bring the runtime to O(n2).
Looking more closely, we can also keep track of the occurrences of only m + 1 and m + 2, and no other values. So, although not required to get AC, we can get rid of the map data structure, and therefore eliminate the logarithmic factor.
The official solution provided here runs in O(n).