[Codeforces] F. Escape Through Leaf

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Escape Through Leaf
Source            : Codeforces
Category          : Data Structure
Algorithm         : Dynamic Convex Hull Trick
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll              long long int  
  
static const int maxn = 2e5 + 5;  
  
// Dynamic Convex Hull Trick  
// Keeps upper hull for maximums.  
// add lines with -m and -b and return -ans to get minimums  
// source : https://codeforces.com/blog/entry/11155?#comment-162462  
  
static const ll is_query = LLONG_MIN;  
  
struct Line  
{  
      ll m, b;  
      mutable function <const Line*()> succ;  
      bool operator < (const Line &rhs) const  
      {  
            if (rhs.b != is_query) return m < rhs.m;  
            const Line *s = succ();  
            if (!s) return 0;  
            ll x = rhs.m;  
            return (b - s->b) < ((s->m - m) * x);  
      }  
};  
  
struct CHT : public multiset <Line>  
{  
      bool bad(iterator y)  
      {  
            auto z = next(y);  
            if (y == begin())  
            {  
                  if (z == end()) return 0;  
                  return y->m == z->m && y->b <= z->b;  
            }  
            auto x = prev(y);  
            if (z == end()) return y->m == x->m && y->b <= x->b;  
            return 1.0 * (x->b - y->b) * (z->m - y->m) >= 1.0 * (y->b - z->b) * (y->m - x->m);  
      }  
      void add(ll m, ll b)  
      {  
            auto y = insert({m, b});  
            y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };  
            if (bad(y)) { erase(y); return; }  
            while (next(y) != end() && bad(next(y))) erase(next(y));  
            while (y != begin() && bad(prev(y))) erase(prev(y));  
      }  
      ll query(ll x)  
      {  
            auto l = *lower_bound((Line){x, is_query} );  
            return l.m * x + l.b;  
      }  
};  
  
CHT *cht[maxn];  
  
vector <int> graph[maxn];  
ll a[maxn], b[maxn], ans[maxn];  
  
void dfs(int u = 1, int p = -1)  
{  
      int sze = 0;  
      cht[u] = new CHT();  
      for (int v : graph[u])  
      {  
            if (v == p) continue;  
            ++sze;  
            dfs(v, u);  
            // Merge smaller to bigger  
            if ((*cht[u]).size() < (*cht[v]).size()) swap(cht[u], cht[v]);  
            for (auto x : (*cht[v])) (*cht[u]).add(x.m, x.b);  
            (*cht[v]).clear();  
      }  
      if (sze == 0) ans[u] = 0;  
      else ans[u] = -(*cht[u]).query(a[u]);  
      (*cht[u]).add(-b[u], -ans[u]);  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tnode;  
      cin >> tnode;  
      for (int i = 1; i <= tnode; i++) cin >> a[i];  
      for (int i = 1; i <= tnode; i++) cin >> b[i];  
      for (int e = 1; e < tnode; e++)  
      {  
            int u, v;  
            cin >> u >> v;  
            graph[u].emplace_back(v);  
            graph[v].emplace_back(u);  
      }  
      dfs();  
      for (int i = 1; i <= tnode; i++) cout << ans[i] << ' ';  
}