{"raw_statement":[{"iden":"statement","content":"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.\n\n<center>![image](https://espresso.codeforces.com/f1269730947b2064639c61332a1db6a5980335b1.png)</center>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 _a__i_.\n\nLet 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_.\n\nWhen 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.\n\nTo 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:\n\n1.  Bank _x_ is _online_. That is, bank _x_ is not hacked yet.\n2.  Bank _x_ is _neighboring_ to some _offline_ bank.\n3.  The strength of bank _x_ is less than or equal to the strength of Inzane's computer.\n\nDetermine the minimum strength of the computer Inzane needs to hack all the banks."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 3·105) — the total number of banks.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the strengths of the banks.\n\nEach of the next _n_ - 1 lines contains two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — meaning that there is a wire directly connecting banks _u__i_ and _v__i_.\n\nIt 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."},{"iden":"output","content":"Print one integer — the minimum strength of the computer Inzane needs to accomplish the goal."},{"iden":"examples","content":"Input\n\n5\n1 2 3 4 5\n1 2\n2 3\n3 4\n4 5\n\nOutput\n\n5\n\nInput\n\n7\n38 -29 87 93 39 28 -55\n1 2\n2 5\n3 2\n2 4\n1 7\n7 6\n\nOutput\n\n93\n\nInput\n\n5\n1 2 7 6 7\n1 5\n5 3\n3 4\n2 4\n\nOutput\n\n8"},{"iden":"note","content":"In the first sample, Inzane can hack all banks using a computer with strength 5. Here is how:\n\n*   Initially, strengths of the banks are \\[1, 2, 3, 4, 5\\].\n*   He hacks bank 5, then strengths of the banks become \\[1, 2, 4, 5,  - \\].\n*   He hacks bank 4, then strengths of the banks become \\[1, 3, 5,  - ,  - \\].\n*   He hacks bank 3, then strengths of the banks become \\[2, 4,  - ,  - ,  - \\].\n*   He hacks bank 2, then strengths of the banks become \\[3,  - ,  - ,  - ,  - \\].\n*   He completes his goal by hacking bank 1.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"尽管 Inzane 成功找到了他心爱的骨头，他的主人 Zane 却仍未归来。为了寻找 Zane，他需要一大笔钱，而他不幸身无分文。为了解决这个问题，他决定黑入银行。\n\n共有 #cf_span[n] 家银行，编号从 #cf_span[1] 到 #cf_span[n]。另有 #cf_span[n - 1] 根电线连接这些银行。所有银行初始均为 _在线_ 状态。每家银行也有其初始强度：银行 #cf_span[i] 的初始强度为 #cf_span[ai]。\n\n在继续之前，我们先定义一些术语。银行 #cf_span[i] 和银行 #cf_span[j] 是 _相邻_ 的，当且仅当存在一根电线直接连接它们。银行 #cf_span[i] 和银行 #cf_span[j] 是 _半相邻_ 的，当且仅当存在一个 _在线_ 的银行 #cf_span[k]，使得银行 #cf_span[i] 和银行 #cf_span[k] _相邻_，且银行 #cf_span[k] 和银行 #cf_span[j] _相邻_。\n\n当一家银行被黑时，它会变为 _离线_（不再 _在线_），而所有与它 _相邻_ 或 _半相邻_ 的银行，其强度会增加 #cf_span[1]。\n\n为启动计划，Inzane 将首先选择一家银行进行黑入。事实上，该银行的强度不能超过他的电脑强度。之后，他将反复选择下一家银行进行黑入，直到所有银行都被黑，但他只能继续黑入银行 #cf_span[x]，当且仅当满足以下所有条件：\n\n请确定 Inzane 黑入所有银行所需的电脑最小强度。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 银行总数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 各银行的强度。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi]) —— 表示有一根电线直接连接银行 #cf_span[ui] 和 #cf_span[vi]。\n\n保证电线的连接方式使得 Inzane 能够使用适当强度的电脑黑入所有银行。\n\n请输出一个整数 —— Inzane 实现目标所需的电脑最小强度。\n\n在第一个样例中，Inzane 可以使用强度为 #cf_span[5] 的电脑黑入所有银行，方法如下：\n\n在第二个样例中，Inzane 可以按顺序黑入银行 #cf_span[4]、#cf_span[2]、#cf_span[3]、#cf_span[1]、#cf_span[5]、#cf_span[7] 和 #cf_span[6]。这样，他可以使用强度为 #cf_span[93] 的电脑黑入所有银行。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 银行总数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 各银行的强度。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi]) —— 表示有一根电线直接连接银行 #cf_span[ui] 和 #cf_span[vi]。保证电线的连接方式使得 Inzane 能够使用适当强度的电脑黑入所有银行。"},{"iden":"output","content":"请输出一个整数 —— Inzane 实现目标所需的电脑最小强度。"},{"iden":"examples","content":"输入51 2 3 4 51 22 33 44 5输出5输入738 -29 87 93 39 28 -551 22 53 22 41 77 6输出93输入51 2 7 6 71 55 33 42 4输出8"},{"iden":"note","content":"在第一个样例中，Inzane 可以使用强度为 #cf_span[5] 的电脑黑入所有银行，方法如下：\n\n初始时，各银行的强度为 #cf_span[[1, 2, 3, 4, 5]]。\n\n他黑入银行 #cf_span[5]，此时各银行强度变为 #cf_span[[1, 2, 4, 5,  - ]]。\n\n他黑入银行 #cf_span[4]，此时各银行强度变为 #cf_span[[1, 3, 5,  - ,  - ]]。\n\n他黑入银行 #cf_span[3]，此时各银行强度变为 #cf_span[[2, 4,  - ,  - ,  - ]]。\n\n他黑入银行 #cf_span[2]，此时各银行强度变为 #cf_span[[3,  - ,  - ,  - ,  - ]]。\n\n他通过黑入银行 #cf_span[1] 完成目标。\n\n在第二个样例中，Inzane 可以按顺序黑入银行 #cf_span[4]、#cf_span[2]、#cf_span[3]、#cf_span[1]、#cf_span[5]、#cf_span[7] 和 #cf_span[6]。这样，他可以使用强度为 #cf_span[93] 的电脑黑入所有银行。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of banks.  \nLet $ G = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $, where each vertex $ i \\in V $ has an initial strength $ a_i \\in \\mathbb{Z} $.  \n\nLet $ N(i) $ denote the set of neighbors of bank $ i $ in $ G $.  \nLet $ S(i) $ denote the set of semi-neighbors of bank $ i $:  \n$$ S(i) = \\{ j \\in V \\setminus \\{i\\} \\mid \\exists k \\in V \\setminus \\{i\\},\\ (i,k) \\in E \\text{ and } (k,j) \\in E \\} $$  \n\nWhen bank $ i $ is hacked:  \n- It becomes offline.  \n- All banks $ j \\in N(i) \\cup S(i) $ have their strengths increased by 1.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 3 \\cdot 10^5 $  \n2. $ -10^9 \\leq a_i \\leq 10^9 $ for all $ i \\in V $  \n3. $ G $ is a tree.  \n\n**Objective**  \nFind the minimum integer $ C $ such that there exists an ordering $ (v_1, v_2, \\dots, v_n) $ of all banks where:  \n- $ C \\geq a_{v_1} $ (first hack requires $ C \\geq $ initial strength),  \n- For each $ k \\in \\{2, \\dots, n\\} $, the strength of bank $ v_k $ at the time of hacking is $ \\leq C $.  \n\nThe strength of bank $ j $ at the time of hacking is:  \n$$ a_j + \\text{number of previously hacked banks that are neighbors or semi-neighbors of } j $$  \n\n**Goal:**  \nMinimize $ C $ such that a valid hacking sequence exists.","simple_statement":null,"has_page_source":false}