fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /* Template Begins */
  6.  
  7. #define FOR(i,N) FORR(i, 0, N)
  8. #define FORR(i,a,b) FOTR(i, a, b, 1)
  9. #define FOTR(i,a,b,c) for(int i=(a);i<(b);i+=(c))
  10. #define FOREACH(it, x) for(__typeof__((x).begin()) it=(x).begin();it!=(x).end();it++)
  11. #define MEM(a,x) memset(a,x,sizeof(a))
  12. #define BCHK(a,x) (((a)>>(x))&1)
  13. #define BSET(a,x) ((a)|(1<<(x)))
  14. #define BCLR(a,x) ((a)&(~(1<<(x))))
  15. #define BTGL(a,x) ((a)^(1<<(x)))
  16. #define FMT(...) (sprintf(CRTBUFF, __VA_ARGS__)?CRTBUFF:0)
  17. #define read() freopen("input.txt","r",stdin)
  18. #define write() freopen("output.txt","w",stdout)
  19. #define cpp_io() {ios_base::sync_with_stdio(false);cin.tie(NULL);}
  20. #define BUFFSIZE 30000
  21. #define INF 1000000000
  22. #define MOD 1000000007
  23. #define MAX 301000
  24. #define pb push_back
  25. #define mkpr make_pair
  26. #define pii pair<int, int>
  27. typedef long long ll;
  28.  
  29. /* Template Ends */
  30.  
  31. int lvl[MAX], C[MAX];
  32. vector<int> G[MAX];
  33.  
  34. int bfs(int u){
  35. queue<int> q;
  36. MEM(lvl, -1);
  37. q.push(u); lvl[u]=0;
  38. int mx = INT_MIN;
  39. while(!q.empty()){
  40. int u = q.front();
  41. int lx = lvl[u];
  42. if(lx>2) lx = 2;
  43. mx=max(mx,lx+C[u]);
  44. q.pop();
  45. for(int i=0; i<G[u].size(); i++){
  46. int v = G[u][i];
  47. if(lvl[v]==-1){
  48. q.push(v);
  49. lvl[v] = lvl[u]+1;
  50. }
  51. }
  52. }
  53. return mx;
  54. }
  55.  
  56. int main(){
  57. //read();
  58. cpp_io();
  59. int n, x, y, maxi, maxc=INT_MIN, mcount=0;
  60. cin>>n;
  61. for(int i=1; i<=n; i++){
  62. cin>>C[i];
  63. if(C[i]>maxc)maxc=C[i];
  64. }
  65. for(int i=0; i<n-1; i++){
  66. cin>>x>>y;
  67. G[y].pb(x);
  68. G[x].pb(y);
  69. }
  70.  
  71. for(int i=1; i<=n; i++){
  72. if(C[i]==maxc){
  73. mcount++;
  74. maxi = i;
  75. }
  76. }
  77. if(mcount==1){
  78. cout<<bfs(maxi)<<"\n";
  79. return 0;
  80. }
  81.  
  82. for(int i=1; i<=n; i++){
  83. int cn = 0;
  84. if(C[i]==maxc)cn++;
  85. for(int j=0; j<G[i].size(); j++){
  86. int u = G[i][j];
  87. if(C[u]==maxc)cn++;
  88. }
  89. if(cn==mcount){
  90. cout<<maxc+1<<"\n";
  91. return 0;
  92. }
  93. }
  94. cout<<maxc+2<<"\n";
  95. }
Runtime error #stdin #stdout 0s 25472KB
stdin
Standard input is empty
stdout
Standard output is empty