fork download
copy 
  1. // Author: 4uckd3v - Nguyen Cao Duc
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int MAX_N = 1e5;
  9. const int MOD = 1e9 + 7;
  10.  
  11. struct Line {
  12.     ll a, b;
  13.     Line() {};
  14.     Line(ll a, ll b) : a(a), b(b) {};
  15.  
  16.     ll eval(int x) { return a * x + b; };
  17.     ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); };
  18.     double intersect(const Line &other) {
  19.         return (double)(other.b - b) / (a - other.a);
  20.     };
  21. };
  22.  
  23. struct State {
  24.     int pos, size;
  25.     Line overwrite;
  26.     State(int pos, int size, Line overwrite) : pos(pos), size(size), overwrite(overwrite) {};
  27. };
  28.  
  29. struct ConvexHullTrick {
  30.     Line line[MAX_N + 5];
  31.     int size;
  32.  
  33.     stack<State> st;
  34.  
  35.     void rollback() {
  36.         assert(!st.empty());
  37.         line[st.top().pos] = st.top().overwrite;
  38.         size = st.top().size;
  39.         st.pop();
  40.     };
  41.  
  42.     void addLine(Line newLine) {
  43.         if (size < 2) {
  44.             st.push(State(size, size, line[size]));
  45.             line[size++] = newLine;
  46.             return;
  47.         };
  48.  
  49.         int l = 0, r = size - 2, pos = size;
  50.         while (l <= r) {
  51.             int mid = (l + r) >> 1;
  52.             if (line[mid].intersect(newLine) <= line[mid].intersect(line[mid + 1])) {
  53.                 pos = mid + 1;
  54.                 r = mid - 1;
  55.             } else
  56.                 l = mid + 1;
  57.         };
  58.  
  59.         st.push(State(pos, size, line[pos]));
  60.         line[pos] = newLine;
  61.         size = pos + 1;
  62.     };
  63.  
  64.     ll query(int x) {
  65.         if (size < 2) return line[0].eval(x);
  66.  
  67.         ll res = line[0].eval(x);
  68.         int l = 0, r = size - 2;
  69.         while (l <= r) {
  70.             int mid = (l + r) >> 1;
  71.             res = min(res, line[mid].eval(x));
  72.             res = min(res, line[mid + 1].eval(x));
  73.             if (line[mid].eval(x) >= line[mid + 1].eval(x))
  74.                 l = mid + 1;
  75.             else
  76.                 r = mid - 1;
  77.         };
  78.  
  79.         return res;
  80.     };
  81. };
  82.  
  83. int n;
  84. int S[MAX_N + 5], V[MAX_N + 5];
  85. ll dp[MAX_N + 5], f[MAX_N + 5];
  86. ConvexHullTrick cht;
  87. vector<ii> adj[MAX_N + 5];
  88. vector<int> ancestor;
  89.  
  90. void dfs(int u, int par) {
  91.     if (u != 1) dp[u] = cht.query(V[u]) + f[u] * V[u] + S[u];
  92.     cht.addLine(Line(-f[u], dp[u]));
  93.  
  94.     for (ii e : adj[u]) {
  95.         int v = e.first, w = e.second;
  96.         if (v == par) continue;
  97.         f[v] = f[u] + w;
  98.         dfs(v, u);
  99.     };
  100.  
  101.     cht.rollback();
  102. };
  103.  
  104. int main() {
  105.     ios_base::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     if (fopen("MAIN.INP", "r")) {
  108.         freopen("MAIN.INP", "r", stdin);
  109.         freopen("MAIN.OUT", "w", stdout);
  110.     };
  111.  
  112.     cin >> n;
  113.     for (int i = 1; i < n; i++) {
  114.         int u, v, w;
  115.         cin >> u >> v >> w;
  116.         adj[u].push_back(ii(v, w));
  117.         adj[v].push_back(ii(u, w));
  118.     };
  119.  
  120.     for (int i = 2; i <= n; i++) cin >> S[i] >> V[i];
  121.  
  122.     dfs(1, 1);
  123.  
  124.     for (int u = 2; u <= n; u++) cout << dp[u] << " ";
  125. };
  126.  
Success #stdin #stdout 0.01s 8484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hSzgsR
language:
C++14 (gcc 8.3)
created:
159 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!