[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] << ' ';  
}  

[UVA Live] ACM Tax

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ACM Tax
Source            : UVA Live
Category          : Data Structure
Algorithm         : Persistent Segment Tree
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. static const int maxn = 1e6 + 5;  
6. static const int logn = 18;  
7.   
8. struct Node  
9. {  
10.       int st;  
11.       int lft, rgt;  
12.       Node(int st = 0, int lft = 0, int rgt = 0) : st(st), lft(lft), rgt(rgt) {}  
13. } Tree[maxn];  
14.   
15. int version[maxn], NODES, N = 100000 + 5;  
16.   
17. int update(int root, int a, int b, int pos, int val)  
18. {  
19.       int newNode = ++NODES;  
20.       Tree[newNode] = Tree[root];  
21.       if (a == b)  
22.       {  
23.             Tree[newNode].st += val;  
24.             return newNode;  
25.       }  
26.       int mid = (a + b) >> 1;  
27.       if (pos <= mid) Tree[newNode].lft = update(Tree[newNode].lft, a, mid, pos, val);  
28.       else Tree[newNode].rgt = update(Tree[newNode].rgt, mid + 1, b, pos, val);  
29.       Tree[newNode].st = Tree[ Tree[newNode].lft ].st + Tree[ Tree[newNode].rgt ].st;  
30.       return newNode;  
31. }  
32.   
33. int query(int root_lca, int root_u, int root_v, int a, int b, int k)  
34. {  
35.       if (a == b) return a;  
36.       int sum = Tree[ Tree[root_u].lft ].st + Tree[ Tree[root_v].lft ].st - 2 * Tree[ Tree[root_lca].lft ].st;  
37.       int mid = a + b >> 1;  
38.       if (sum >= k) return query(Tree[root_lca].lft, Tree[root_u].lft, Tree[root_v].lft, a, mid, k);  
39.       else return query(Tree[root_lca].rgt, Tree[root_u].rgt, Tree[root_v].rgt, mid+1, b, k - sum);  
40. }  
41.   
42. struct GNode  
43. {  
44.       int v, w;  
45.       GNode(int v = 0, int w = 0) : v(v), w(w) {}  
46. };  
47.   
48. vector <GNode> graph[maxn];  
49. int depth[maxn], father[maxn][logn];  
50.   
51. void dfs(int u = 1, int p = -1)  
52. {  
53.       for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];  
54.       for (GNode it : graph[u])  
55.       {  
56.             int v = it.v;  
57.             int w = it.w;  
58.             if (v == p) continue;  
59.             depth[v] = depth[u] + 1;  
60.             father[v][0] = u;  
61.             version[v] = update(version[u], 1, N, w, 1);  
62.             dfs(v, u);  
63.       }  
64. }  
65.   
66. int lca(int u, int v)  
67. {  
68.       if (depth[u] < depth[v]) swap(u, v);  
69.       for (int i = logn-1; i >= 0; i--) if (depth[ father[u][i] ] >= depth[v]) u = father[u][i];  
70.       if (u == v) return u;  
71.       for (int i = logn-1; i >= 0; i--) if (father[u][i] != father[v][i]) u = father[u][i], v = father[v][i];  
72.       return father[u][0];  
73. }  
74.   
75. void clean()  
76. {  
77.       NODES = 0;  
78.       for (int i = 0; i < maxn; i++)  
79.       {  
80.             Tree[i] = Node();  
81.             version[i] = 0;  
82.             graph[i].clear();  
83.             depth[i] = 0;  
84.             fill(begin(father[i]), end(father[i]), 0);  
85.       }  
86. }  
87.   
88. signed main()  
89. {  
90.       ios_base::sync_with_stdio(false);  
91.       cin.tie(nullptr);  
92.       cout.tie(nullptr);  
93.       cout << fixed << setprecision(1);  
94.   
95.       #ifndef ONLINE_JUDGE  
96.             freopen("in.txt", "r", stdin);  
97.       #endif // ONLINE_JUDGE  
98.   
99.   
100.       int tc;  
101.       cin >> tc;  
102.       for (int tcase = 1; tcase <= tc; tcase++)  
103.       {  
104.             clean();  
105.   
106.             int tnode;  
107.             cin >> tnode;  
108.             for (int e = 1; e < tnode; e++)  
109.             {  
110.                   int u, v, w;  
111.                   cin >> u >> v >> w;  
112.                   graph[u].emplace_back(v, w);  
113.                   graph[v].emplace_back(u, w);  
114.             }  
115.             version[0] = 0;  
116.             version[1] = update(version[0], 1, N, 4, 0);  
117.             depth[1] = 1;  
118.             dfs();  
119.   
120.             int tqeury;  
121.             cin >> tqeury;  
122.             for (int q = 1; q <= tqeury; q++)  
123.             {  
124.                   int u, v;  
125.                   cin >> u >> v;  
126.                   int lcax = lca(u, v);  
127.                   int d = depth[u] + depth[v] - 2 * depth[lcax];  
128.                   int k = (d+1) / 2;  
129.                   double ans = (double)query(version[lcax], version[u], version[v], 1, N, k);  
130.                   if (~d & 1)  
131.                   {  
132.                         ans += (double)query(version[lcax], version[u], version[v], 1, N, k+1);  
133.                         ans /= 2.0;  
134.                   }  
135.                   cout << ans << '\n';  
136.             }  
137.       }  
138. }