fork download
copy 
  1. 					// ADASALES SPOJ    https://w...content-available-to-author-only...j.com/problems/ADASALES/
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("avx,avx2,fma")
  4. #pragma GCC optimization("unroll-loops")
  5. #include<iostream>
  6. #include<bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  10. #define ll long long 
  11. #define vec vector<ll> 
  12. #define mk make_pair 
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define setbit(n) __builtin_popcountll(n)
  16. #define rep(i,a,b) for(int i=a; i<=b;i++) 
  17. #define rep1(i,n)  for(int i=0;i<n;i++)
  18. #define rrep(i,a,b) for(int i=a; i>=b;i--) 
  19. #define rrep1(i,n)  for(int i=n;i>=0;i--)
  20. #define cin(arr,n) for(int i=0; i<n;i++){cin>>arr[i];}
  21. #define cin1(vec,n) rep1(i,n){ll x;cin>>x;vec.pb(x);}
  22. #define so(vec) sort(vec.begin(),vec.end())
  23. #define rev(v) reverse(v.begin(),v.end())
  24. #define cout(v) rep1(i,v.size()){cout<<v[i]<<" ";}
  25. #define prdouble(x) cout<<fixed<<setprecision(10)<<x;
  26. #define out(v) cout<<v<<" "; 
  27. #define all(v) v.begin(),v.end()
  28. #define yes cout<<"YES";
  29. #define no cout<<"NO";
  30. #define no1 cout<<"-1";
  31. #define lb cout<<"\n";
  32. template <typename T>
  33. T myMax(T x, T y)
  34. {
  35. return (x > y) ? x : y;
  36. }
  37. const ll N = 1e5+7;
  38. const ll M = 2e9+7;
  39. const ll Mn = -(1e9+7);
  40. using namespace std;
  41. using namespace __gnu_pbds;
  42. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  43. #define ordered_multiset tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
  44.  
  45. //For policy based data structures:-
  46. //order_of_key (K): Number of items strictly smaller than K
  47. //find_by_order(k): Kth element in a Set (counting from zero)
  48. //deleting element in ordered multiset:-
  49. //ordered_multiset::iterator it = v.find_by_order(v.order_of_key(a[i]));
  50. //v.erase(it);
  51. //deleting element in ordered set:-
  52. //ordered_set::iterator it = v.find_by_order(v.order_of_key(a[i]));
  53. //v.erase(it);
  54.  
  55. vector<ll> v;
  56. vector<ll> g[N];
  57. // ll visi[N];
  58. ll in[N];
  59. ll out[N];
  60.  
  61. void dfs1(ll node, ll par){ // filling in 
  62.     for(auto it:g[node]){
  63.         if(it!=par){
  64.             dfs1(it,node);
  65.             // cout<<node<<" : "<<it<<" "<<in[it];lb;
  66.             in[node] = max({in[node],in[it]+max(0LL,v[it]-v[node])});
  67.         }
  68.     }
  69. }
  70.  
  71. void dfs2(ll node,ll par){ // filling out
  72.     ll mx1=-1;
  73.     ll mx2=-1;
  74.     for(auto it:g[node]){
  75.         if(it!=par){
  76.             if(in[it]+max(0LL,v[it]-v[node])>mx1){
  77.                 mx2=mx1;
  78.                 mx1=in[it]+max(0LL,v[it]-v[node]);
  79.             }
  80.             else if(in[it]+max(0LL,v[it]-v[node])>mx2){
  81.                 mx2=in[it]+max(0LL,v[it]-v[node]);
  82.             }
  83.         }
  84.     }
  85.     for(auto it:g[node]){
  86.         if(it!=par){
  87.             ll use=mx1;
  88.             if(mx1==in[it]+max(0LL,v[it]-v[node])){
  89.                 use=mx2;
  90.             }
  91.             out[it]=max({out[it],use+max(0LL,v[node]-v[it]),out[node]+max(0LL,v[node]-v[it])});
  92.             dfs2(it,node);
  93.         }
  94.     }
  95.  
  96. }
  97.  
  98. void solve(){
  99.     ll n,q;
  100.     cin>>n>>q;
  101.     cin1(v,n);
  102.     for(int i=0;i<n-1;i++){
  103.         ll a,b;
  104.         cin>>a>>b;
  105.         g[a].pb(b);
  106.         g[b].pb(a);
  107.     }
  108.     ll par=-1;
  109.     dfs1(0LL,par);
  110.     // for(int i=0;i<n;i++){
  111.     //     cout<<i<<" "<<in[i]<<" ";
  112.     // }
  113.     dfs2(0LL,par);
  114.     for(int i=0;i<q;i++){
  115.         ll x;
  116.         cin>>x;
  117.         cout<<max(in[x],out[x]);lb;
  118.     }
  119. }
  120. int main(){
  121. fast;
  122. ll t;
  123. t=1;
  124. // cin>>t;
  125. rep1(i,t){
  126. solve();
  127. // cout<<"\n";
  128. }
  129.     return 0;
  130. }
Success #stdin #stdout 0.01s 7236KB
comments (?)
stdin
copy 
6 6
1 2 3 4 5 4
1 0
1 2
1 3
3 4
4 5
0
1
2
3
4
5
stdout
copy 
4
3
3
1
1
2
https://ideone.com/vbejsW
language:
C++ (gcc 8.3)
created:
2 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!