[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. }