fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> 
  3. #include <ext/pb_ds/tree_policy.hpp> 
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds; 
  7.  
  8. typedef     unsigned long long int ull;
  9. typedef     long long int    ll;
  10. typedef     long double      ld;
  11. typedef     pair<ll,ll>      pll;
  12. #define     FOR(i,a,b)       for(ll i=a;i<b;i++)
  13. #define     FORE(i,a,b)      for(int i=a;i<=b;i++)
  14. #define     FORD(i,b,a)      for(int i=b;i>a;i--)
  15. #define     FORDE(i,b,a)     for(ll i=b;i>=a;i--)
  16. #define     debug(x)         cout<< '>'<<#x<<" : "<<x<<"\n";
  17. #define     debug2(x,y)      cout<< '>'<<#x<<" : "<<x<<"\n"; cout<< '>'<<#y<<" : "<<y<<"\n";
  18. #define     debug3(x,y,z)    cout<< '>'<<#x<<" : "<<x<<"\n"; cout<< '>'<<#y<<" : "<<y<<"\n";cout<< '>'<<#z<<" : "<<z<<"\n";
  19. #define     umap             unordered_map
  20. #define     uset             unordered_set
  21. #define     lb               lower_bound
  22. #define     ub               upper_bound
  23. #define     mp               make_pair
  24. #define     in               insert
  25. #define     s                second
  26. #define     f                first
  27. #define     nn               cout<<"\n"
  28. #define     pb               push_back
  29. #define     testcase         int t;cin>>t;while(t--)
  30. #define     gcd(a,b)         __gcd(a,b)
  31. #define     maxv             INT_MAX
  32. #define     minv             INT_MIN
  33. #define     MOD              1000000007
  34. #define     SACHITJAGGI      ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
  35. #define     here             cout<<"I'm here\n";
  36. #define     flush            cout.flush();
  37. #define endl '\n'         
  38. #define     all(x)           (x).begin(),(x).end()
  39. #define     setcount(x)      __builtin_popcountll(x)
  40. #define ordered_set_single tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
  41.  
  42. typedef tree<
  43. pair<ll, ll>,
  44. null_type,
  45. less<pair<ll,ll>>,
  46. rb_tree_tag,
  47. tree_order_statistics_node_update> ordered_set_pair;
  48.  
  49. inline int add(int a,int b) { return (a%MOD + b%MOD + MOD)%MOD; }
  50. inline int mul(int a,int b) { return (a%MOD * b%MOD + MOD)%MOD; }
  51. inline int sub(int a,int b) { return (a%MOD - b%MOD + MOD)%MOD; }
  52.  
  53. template<class T> void dispvector(vector<T> v){ for(int i=0;i<v.size();i++) cout<<v[i]<<" "; cout << "\n"; }
  54.  
  55. ll power(ll x, ll y, ll p) 
  56. { 
  57.     ll res = 1;      // Initialize result 
  58.  
  59.     x = x % p;  // Update x if it is more than or 
  60.                 // equal to p 
  61.  
  62.     while (y > 0) 
  63.     { 
  64.         // If y is odd, multiply x with result 
  65.         if (y & 1) 
  66.             res = (res*x) % p; 
  67.  
  68.         // y must be even now 
  69.         y = y>>1; // y = y/2 
  70.         x = (x*x) % p; 
  71.     } 
  72.     return res; 
  73. } 
  74.  
  75. ll modInverse(ll n, ll p) 
  76. { 
  77.     return power(n, p-2, p); 
  78. } 
  79.  
  80. vector<ll> solve(ll curr,ll parent, vector<vector<ll>>& graph, vector<ll>& mini,vector<ll>& maxi)
  81. {
  82.  
  83.     vector<ll> answ(16,0);
  84.     ll m1=maxi[curr];
  85.     ll m2=mini[curr];
  86.     ll m3=(m1+m2)/2ll;
  87.     ll m4=(m1+m2+1ll)/2ll;
  88.  
  89.  
  90.     // m1
  91.     // m2
  92.     // m3
  93.  
  94.     vector<ll> strg{m1,m2,m3,m4};
  95.  
  96.     for(auto u:graph[curr])
  97.     {
  98.         if(u!=parent)
  99.         {
  100.                 vector<ll> tmp=solve(u,curr,graph,mini,maxi);
  101.  
  102.                 ll tm1=maxi[u];
  103.                 ll tm2=mini[u];
  104.                 ll tm3=(tm1+tm2)/2ll;
  105.                 ll tm4=(tm1+tm2+1ll)/2ll;
  106.  
  107.  
  108.                 vector<ll> tmp3{tm1,tm2,tm3,tm4};
  109.  
  110.  
  111.                 FOR(i,0,4)
  112.                 {
  113.                     FOR(j,0,4)
  114.                     {
  115.                         answ[4*i+j]+=(abs(strg[i]-tmp3[j])+tmp[j]);
  116.                     }
  117.                 }
  118.  
  119.  
  120.             // cout<<maxi[curr]<<" "<<mini[curr]<<endl;
  121.             // cout<<maxi[u]<<" "<<mini[u]<<endl;
  122.  
  123.         }
  124.     }
  125.     vector<ll> ans(4,0);
  126.     FOR(i,0,16)
  127.     {
  128.         ans[i/4]=max(answ[i],ans[i/4]);
  129.     }
  130.     // cout<<curr<<" "<<endl;
  131.     // dispvector<ll>(strg);
  132.     // dispvector<ll>(ans);
  133.  
  134.  
  135.     return ans;
  136.  
  137. }
  138.  
  139.  
  140. signed main(int argc, char** argv)
  141. {
  142.     #ifndef ONLINE_JUDGE
  143.     freopen("input.txt", "r", stdin);
  144.     freopen("output.txt", "w", stdout);
  145.     #endif
  146.     SACHITJAGGI
  147.     long t=1;
  148.     cin>>t;
  149.     while(t--)
  150.     {
  151.         ll n;
  152.         cin>>n;
  153.         vector<vector<ll>> graph(n+1,vector<ll>());
  154.         vector<ll> mini(n+1);
  155.         vector<ll> maxi(n+1);
  156.  
  157.         FOR(i,1,n+1) cin>>mini[i]>>maxi[i];
  158.  
  159.         FOR(i,0,n-1)
  160.         {
  161.             ll a,b;
  162.             cin>>a>>b;
  163.             graph[a].pb(b);
  164.             graph[b].pb(a);
  165.         }
  166.  
  167.         vector<ll> tmp= solve(1,-1,graph,mini,maxi);
  168.         // dispvector<ll>(tmp);
  169.         cout<<max(max(tmp[0],tmp[3]),max(tmp[2],tmp[1]))<<endl;
  170.  
  171.     }
  172.     return 0;
  173. }
Runtime error #stdin #stdout #stderr 0s 5488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/zEdYYE
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!