fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. #define MAX 200200
  6. #define inf 1000000000
  7. #define pb push_back
  8.  
  9. struct node
  10. {
  11.     ll fi;
  12.     ll se;
  13.  
  14.     node(int _fi = -inf, int _se = -inf)
  15.     {
  16.         fi = _fi;
  17.         se = _se;
  18.     }
  19.  
  20.     void add(const node& other)
  21.     {
  22.         if(other.fi > this->fi){
  23.             this->se = this->fi;
  24.             this->fi = other.fi;
  25.         }else if(other.fi > this->se){
  26.             this->se = other.fi;
  27.         }
  28.     }
  29. };
  30.  
  31. int n;
  32. vector<int> adj[MAX];
  33. bool ok[MAX];
  34. int w[MAX], ans[MAX];
  35. node f[MAX];
  36.  
  37. void nhap()
  38. {
  39.     cin >> n;
  40.     for(int i = 1; i<=n; i++) cin >> w[i];
  41.     for(int i = 1; i<=n-1; i++){
  42.         int a,b; cin >> a >> b;
  43.         adj[a].pb(b);
  44.         adj[b].pb(a);
  45.     }
  46.     memset(ok,true,sizeof(ok));
  47. }
  48.  
  49. void pre_compute()
  50. {
  51.     ok[1] = ok[0] = false;
  52.     for(int i = 2; i*i <=n; i++){
  53.         if(ok[i]){
  54.             for(int j = i*i; j<=n; j+= i) ok[j] = false;
  55.         }
  56.     }
  57. }
  58.  
  59. void dfs(int v, int par)
  60. {
  61.     f[v].se = -inf;
  62.     f[v].fi = (ok[v])? w[v] : -inf;
  63.     for(int u : adj[v]){
  64.         if(u == par) continue;
  65.         dfs(u,v);
  66.         if(f[u].fi != -inf){
  67. //            f[v].add(f[u]);
  68.             f[v].add(node(f[u].fi + w[v], f[u].se + w[v]));
  69.         }
  70.     }
  71. }
  72.  
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(0); cin.tie(0);
  76.     nhap();
  77.     pre_compute();
  78.     dfs(1,-1);
  79.     ll res = -inf;
  80.     for(int i = 1; i<=n; i++) res = max(res, 1LL*(f[i].fi + f[i].se) - w[i]);
  81. //    cout << res;
  82.     ll mxtmp = -inf;
  83.     for(int i = 1; i<=n; i++) if(ok[i]) mxtmp = max(mxtmp , 1LL*w[i]);
  84.     cout << max(res, mxtmp);
  85. //    for(int i = 1; i<=n; i++) cout << ans[i] << ' ';
  86. //    cout << f[1].fi << ' ' << f[1].se;
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 13244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1000000000
https://ideone.com/IxHyj2
language:
C++14 (gcc 8.3)
created:
17 hours 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!