fork(4) download
  1. #include <stdio.h>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int a[300005];
  6. vector<int> way[300005];
  7.  
  8. int main(){
  9. int n;
  10. scanf("%d", &n);
  11. int maxval=-1e9;
  12. for(int i=1; i<=n; i++) scanf("%d", &a[i]), maxval = max(maxval, a[i]);
  13. for(int i=0; i<n-1; i++){
  14. int u, v;
  15. scanf("%d%d", &u, &v);
  16. way[u].push_back(v);
  17. way[v].push_back(u);
  18. }
  19. int x=0, y=0;
  20. for(int i=1; i<=n; i++){
  21. if(a[i] == maxval) x++;
  22. else if(a[i] == maxval-1) y++;
  23. }
  24.  
  25. int res = maxval+2;
  26.  
  27. for(int i=1; i<=n; i++){
  28.  
  29. // minus
  30. if(a[i] == maxval) x--;
  31. else if(a[i] == maxval-1) y--;
  32. for(int j=0; j<way[i].size(); j++){
  33. int pos = way[i][j];
  34. if(a[pos] == maxval) x--, y++;
  35. else if(a[pos] == maxval-1) y--;
  36. }
  37.  
  38. // check the needed strength and update the answer
  39. if(x == 0){
  40. res = min(res, maxval+1);
  41. if(y == 0) res = min(res, maxval);
  42. }
  43.  
  44. // plus
  45. if(a[i] == maxval) x++;
  46. else if(a[i] == maxval-1) y++;
  47. for(int j=0; j<way[i].size(); j++){
  48. int pos = way[i][j];
  49. if(a[pos] == maxval) x++, y--;
  50. else if(a[pos] == maxval-1) y++;
  51. }
  52.  
  53. }
  54.  
  55. printf("%d", res);
  56.  
  57. return 0;
  58. }
Runtime error #stdin #stdout 0s 23440KB
stdin
Standard input is empty
stdout

Standard output is empty