fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w6Y77d
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!