fork download
copy 
  1. // Author: Muhammed Khaled Shoeib
  2.  
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. using namespace std;
  8. //....................................................
  9. // struct to speed-up the unordered data structures like map/set.
  10. struct hash_function // unordered + modified hash >> ordered
  11. {   static uint64_t splitmix64(uint64_t x) {
  12.         x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  13.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
  14.     size_t operator()(uint64_t x) const {
  15.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  16.         return splitmix64(x + FIXED_RANDOM); } };
  17. //....................................................
  18. template < typename T, typename Compare = less < T > > // O(logn)
  19. using ordered_set = tree < T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
  20. // less_equal:    asc.  not_unique, st.order_of_key(k) --> no. of items < k,  less: unique
  21. // greater_equal: desc. not_unique, st.order_of_key(k) --> no. of items > k,  greater: unique
  22. // *st.find_by_order(k) --> st[k] (Zero-indexed)
  23. // less_equal (u can't erase here!) == multi-set
  24. template < typename T > using maxpq = priority_queue < T >;
  25. template < typename T > using minpq = priority_queue < T, vector< T >, greater< T > >;
  26. //....................................................
  27. #define     boost                  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  28. #define     precision(a)           cout << fixed << setprecision(a)
  29. #define     alo                    cout << "alooooooooooo!" << endl
  30. #define     YES                    cout << "YES" << endl
  31. #define     Yes                    cout << "Yes" << endl
  32. #define     yes                    cout << "yes" << endl
  33. #define     NO                     cout << "NO" << endl
  34. #define     No                     cout << "No" << endl
  35. #define     no                     cout << "no" << endl
  36. #define     ne                     cout << -1 << endl
  37. #define     endl                   "\n"
  38. #define     mem(mat, val)          memset(mat, val, sizeof(mat))
  39. #define     ones(x)               __builtin_popcountll(x)
  40. #define     msb(x)                63ll - __builtin_clzll(x)
  41. #define     lsb(x)                __builtin_ffsll(x) - 1ll
  42. //....................................................
  43. #define     all(x)                 x.begin(), x.end()
  44. #define     rall(x)                x.rbegin(),x.rend()
  45. #define     _ceil(a, b)            (((ll)(a) + (ll)(b - 1)) / (ll)(b)) // up
  46. #define     _floor(a, b)           (a / b) // down
  47. #define     _round(a, b)           ((a + (b / 2ll)) / b) // nearest
  48. //....................................................
  49. // using ll  = int;                                                                     // take care of this shit!
  50. using ll  = long long;
  51. using i64 = long long; using i32 = int; using lli = long long int; using LL = __int128;
  52. using ld  = long double; using LD = __float128; using ull = unsigned long long;
  53. using cld = complex < long double >; using cd = complex < double >;
  54. //......................................................
  55. ll _gcd(ll x, ll y) { return y ? _gcd(y, x % y) : x; } // O(log(min(x, y)))
  56. ll _lcm(ll a, ll b) { ll g = _gcd(a, b); return (a * b) / g; }
  57. //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  58. //#define getrand(l, r) uniform_int_distribution<long long>(l, r)(rng)
  59. //......................................................
  60. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  61. int dx_diag[4] = { 1, 1, -1, -1 }, dy_diag[4] = { 1, -1, -1, 1 };
  62. int dx_all[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy_all[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  63. int dx_knight[8] = {2, 2, 1, 1, -2, -2, -1, -1}, dy_knight[8] = {1, -1, 2, -2, 1, -1, 2, -2};
  64. const ld  pi  = acos(-1); // 3.141592653589793238462643383279
  65. const ld eps = 1e-9;
  66. // const ll inf = (ll)INT32_MAX; // 2e9
  67. const ll oo = (ll)1e18;       // 1e15 (may cause OF in DP, Binary Search, ...)
  68. const ll OO = (ll)INT64_MAX;  // 9e18
  69. const ll mod  = (ll)1e9 + 7;  // 1e9 + 7, 998244353
  70. //..................................................... // string(len, char);
  71. /*
  72.  * think twice, code once.
  73.  * think of different approaches to tackle a problem, write them down.
  74.  * think of different views of the problem, don't look from only one side.
  75.  * don't get stuck in one approach/problem.
  76.  * common mistakes: line 49, overflow (sum of many numbers), corner cases (n = 1), over/under count, infinite loops,
  77.  * TLE, MLE (int instead of ll, using memset, Recursive DP, ...), RTE (out of bounds indexing), ....
  78.  */
  79. ///____________________________________________ Shoeib __________________________________________________________
  80.  
  81.  
  82. // log(n) for insert & eval,  O(1) for rollback.
  83. // All lines should be added in strictly increasing slope order.
  84.  
  85. class PersistentCHT
  86. {
  87.     struct Line
  88.     {
  89.         ll m, c;
  90.         Line() { }
  91.         Line(ll _m, ll _c) : m(_m), c(_c) { }
  92.     };
  93.  
  94.     vector < vector < Line > > hull;
  95.     vector < ll > version_idx;
  96.     vector < ll > version_sz;
  97.     ll SZ = 0;
  98.  
  99.     ld inter(Line t1, Line t2)
  100.     {
  101.         ld ret;
  102.         ret = (ld)(t2.c - t1.c - .0)/(t1.m - t2.m - .0);
  103.         return ret;
  104.     }
  105.  
  106.     void insert_line(Line curr)
  107.     {
  108.         Line temp, temp2;
  109.         version_sz.push_back(SZ);
  110.  
  111.         if(SZ > 1)
  112.         {
  113.             ll s = 0, e = SZ - 1;
  114.  
  115.             while(s < e)
  116.             {
  117.                 ll p = (s + e) / 2;
  118.  
  119.                 temp = hull[p + 1].back();
  120.                 temp2 = hull[p].back();
  121.  
  122.                 ld point = inter(temp, temp2);
  123.                 ld point2 = inter(temp, curr);
  124.  
  125.                 if(point < point2) s = p+1;
  126.                 else e = p;
  127.             }
  128.             SZ = s + 1;
  129.         }
  130.  
  131.         if(hull.size() == SZ)
  132.         {
  133.             vector<Line> x;
  134.             hull.push_back(x);
  135.         }
  136.  
  137.         hull[SZ].push_back(curr);
  138.         version_idx.push_back(SZ);
  139.         SZ++;
  140.     }
  141.  
  142. public:
  143.  
  144.     void insert_line(ll m, ll c){ insert_line(Line(m, c)); }
  145.  
  146.     ll eval(ll find)
  147.     {
  148.         ll s = 0, e = SZ - 1;
  149.  
  150.         while(s < e)
  151.         {
  152.             ll p = (s + e) / 2;
  153.             ld point = inter(hull[p].back(), hull[p + 1].back());
  154.             if(point < find) s = p + 1;
  155.             else e = p;
  156.         }
  157.  
  158.         ll ret = (hull[s].back().m * find) + hull[s].back().c;
  159.         return ret;
  160.     }
  161.  
  162.     void rollback()
  163.     {
  164.         SZ = version_sz.back();
  165.         version_sz.pop_back();
  166.         hull[version_idx.back()].pop_back();
  167.         version_idx.pop_back();
  168.     }
  169.  
  170.     ll  size() { return SZ; }
  171.  
  172. };
  173.  
  174.  
  175. // ...........
  176.  
  177.  
  178. ll n;
  179. vector < vector < pair < ll, ll > > > graph;
  180. vector < ll > s, v, dp;
  181.  
  182.  
  183. // dp[u] = min(s[u] + (dist[u] - dist[v])*v[u] +  dp[v]) --> from u to it's ancestor v.
  184. // dp[u] = min(s[u] + dist[u]*v[u] - dist[v]*v[u] + dp[v])
  185. // dp[u] = min(s[u] + dist[u]*v[u]  +   m   * x  +    c  )
  186.  
  187.  
  188. PersistentCHT pcht;
  189.  
  190. void dfs(ll root, ll par, ll dist)
  191. {
  192.     if(root != 1) dp[root] = s[root] + dist*v[root] + -1*pcht.eval(v[root]);
  193.  
  194.     pcht.insert_line(dist, -dp[root]);
  195.  
  196.     for(const auto &i : graph[root])
  197.     {
  198.         if(i.first == par) continue;
  199.         dfs(i.first, root, dist + i.second);
  200.     }
  201.  
  202.     pcht.rollback();
  203.  
  204. }
  205.  
  206.  
  207.  
  208. void solve()
  209. {
  210.  
  211.     cin >> n;
  212.     graph.resize(n + 1);
  213.     for(ll i = 1; i <= n - 1; i++)
  214.     {
  215.         ll u, v, d; cin >> u >> v >> d;
  216.         graph[u].push_back({v, d});
  217.         graph[v].push_back({u, d});
  218.     }
  219.  
  220.     s.resize(n + 1); v.resize(n + 1);
  221.     for(ll i = 2; i <= n; i++) cin >> s[i] >> v[i];
  222.  
  223.  
  224.     dp.resize(n + 1);
  225.  
  226.  
  227.     dfs(1, 0, 0);
  228.  
  229.     for(ll i = 2; i <= n; i++) cout << dp[i] << ' ';
  230.     cout << endl;
  231.  
  232.  
  233.  
  234.     return;
  235. }
  236.  
  237.  
  238. signed main()
  239. {
  240.     boost;
  241.  
  242.     // freopen("bank.in", "r", stdin);
  243.     // freopen("bank.out", "w", stdout);
  244.  
  245.     // precision(15);
  246.  
  247.     i32 _ = 1; //cin >> _;
  248.     // cout.flush();
  249.     while(_--) solve();
  250.     return 0;
  251. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
5 
1 2 20 
2 3 12 
2 4 1 
4 5 3 
26 9 
1 10 
500 2 
2 30
stdout
copy 
206 321 542 328
https://ideone.com/oqS6LO
language:
C++14 (gcc 8.3)
created:
263 days ago
visibility:
secret

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!