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 neighboringand 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 bankx 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.Determine the minimum strength of the computer Inzane needs to hack all the banks.
InputThe 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.
OutputPrint 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 NoteIn 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.
Source
Codeforces Round #408 (Div. 2)
My Solution
题意：有一棵无根树，上面每个节点都有一个权值，可以任意选择一个节点删除，但这是和它相邻的节点即隔一个点间接相邻的点 的权值都会增加1，求把所有的点都依次删除，中途会遇到的最大权值点的 最小权值。
无根树、贪心、枚举
其实选定一个根时，根的权值是本身val[i]，根的子节点的权值是val[i]+1，其它节点的权值是 val[i]+2,
这个时候只要枚举根和这个根的直接子节点，即可求出答案。
其中取出的这些节点放在priority_queue1里剩余的其它节点放在priority——queue2里，这样就可以快速的求出剩余节点里的最大的权值了。
然后就可以求出这种取法的时候的 最大权值，然后跟ans取最小值即可。
所有的节点都会被枚举到2、3次，总共O(n),
然后中途用的优先队列来维护，
所以复杂度为 O(nlogn)
[cpp] view plain copy #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; typedef long long LL; const int MAXN = 3e5 + 8; //vector<int> sons[MAXN]; int head[MAXN], tot; struct esge{ int u, v, w, nxt; } a[2*MAXN]; inline void add(int u, int v, int w) { tot++; a[tot].u = u, a[tot].v = v, a[tot].w = w; a[tot].nxt = head[u], head[u] = tot; } int val[MAXN]; priority_queue<int> pq1, pq2; queue<int> que; int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, i, j, k, u, v, ans = 2e9, sz, t; cin >> n; for(i = 1; i <= n; i++){ cin >> val[i]; pq2.push(val[i]); } tot = 1; for(i = 1; i < n; i++){ cin >> u >> v; add(u, v, 1); add(v, u, 1); } if(n == 1){ ans = val[1]; } for(i = 1; i <= n; i++){ if(n == 1)break; //sz = sons[i].size(); pq1.push(val[i]); t = val[i]; for(k = head[i]; k; k = a[k].nxt){ //if(a[k].v == fa) continue; v = a[k].v; //for(j = 0; j < sz; j++){ pq1.push(val[v]); t = max(t, val[v] + 1); } while(!pq1.empty() && pq1.top() == pq2.top()){ pq1.pop(); que.push(pq2.top()); pq2.pop(); } if(!pq2.empty()) ans = min(ans, max(t, pq2.top() + 2)); else ans = min(ans, t); while(!que.empty()){ pq2.push(que.front()); que.pop(); } while(!pq1.empty()){ pq1.pop(); } } cout << ans << endl; #ifdef LOCAL while(!pq1.empty()) pq1.pop(); while(!pq2.empty()) pq2.pop(); memset(a, 0, sizeof a); memset(head, 0, sizeof head); cout << endl; } #endif // LOCAL return 0; }
Thank you!
------from ProLights
