Advertisement
Guest User

Untitled

a guest
Sep 30th, 2015
498
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.19 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cassert>
  6. using namespace std;
  7. vector<int>g[100007];
  8. int parent[100007][22];
  9. int sz[100007];
  10. bool used[100007];
  11. int block[100007], blockpos[100007];
  12. int tin[100007], tout[100007], h[100007];
  13. int timer = 1;
  14. void dfs(int v, int p = 1, int curh = 1)
  15. {
  16. used[v] = true;
  17. parent[v][0] = p;
  18. sz[v] = 1;
  19. h[v] = curh;
  20. tin[v] = timer;
  21. timer++;
  22. for (int j = 1; j < 22; j++)
  23. {
  24. parent[v][j] = parent[parent[v][j - 1]][j - 1];
  25. }
  26. for (int i = 0; i < g[v].size(); i++)
  27. {
  28. int to = g[v][i];
  29. if (!used[to])
  30. {
  31. dfs(to, v, curh + 1);
  32. sz[v] += sz[to];
  33. }
  34. }
  35. tout[v] = timer;
  36. timer++;
  37. }
  38. bool isHeavy(int u, int v)
  39. {
  40. if (sz[u] > sz[v]) swap(u, v);
  41. return 2 * sz[u] > sz[v];
  42. }
  43. bool isAncestor(int u, int v)
  44. {
  45. return tin[u] < tin[v] && tout[u] > tout[v];
  46. }
  47. struct segment_tree
  48. {
  49. vector<long long>tree;
  50. void init(int n)
  51. {
  52. tree.resize(4 * n + 2);
  53. }
  54. void add(int v, int tl, int tr, int pos, int val)
  55. {
  56. if (tl == tr)
  57. {
  58. tree[v] += val;
  59. }
  60. else
  61. {
  62. int tm = (tl + tr) / 2;
  63. if (pos <= tm)
  64. {
  65. add(2 * v, tl, tm, pos, val);
  66. }
  67. else
  68. {
  69. add(2 * v + 1, tm + 1, tr, pos, val);
  70. }
  71. tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  72. }
  73. }
  74. long long getMax(int v, int tl, int tr, int l, int r)
  75. {
  76. if (r<tl || l>tr) return 0;
  77. if (tl >= l && tr <= r) return tree[v];
  78. int tm = (tl + tr) / 2;
  79. return max(getMax(2 * v, tl, tm, l, r), getMax(2 * v + 1, tm + 1, tr, l, r));
  80. }
  81. };
  82. struct hldBlock
  83. {
  84. segment_tree st;
  85. int downv, upv, size;
  86. void init(int _downv, int _upv, int _size)
  87. {
  88. downv = _downv;
  89. upv = _upv;
  90. size = _size;
  91. st.init(size + 1);
  92. }
  93. long long get(int u, int v)
  94. {
  95. if (isAncestor(u, upv) || isAncestor(downv, v))
  96. {
  97. return 0;
  98. }
  99. int l = downv, r = upv;
  100. if (isAncestor(u, downv))
  101. {
  102. l = u;
  103. }
  104. if (isAncestor(upv, v))
  105. {
  106. r = v;
  107. }
  108. return st.getMax(1, 1, size, blockpos[l], blockpos[r]);
  109. }
  110. void change(int v, int val)
  111. {
  112. st.add(1, 1, size, blockpos[v], val);
  113. }
  114. };
  115. hldBlock blocks[100007];
  116. void buildDecomposition(int n)
  117. {
  118. dfs(1);
  119. int bcnt = 1;
  120. for (int i = 1; i <= n; i++)
  121. {
  122. bool hasHeavy = false;
  123. for (int j = 0; j < g[i].size(); j++)
  124. {
  125. int to = g[i][j];
  126. if (to == parent[i][0]) continue;
  127. if (isHeavy(i, to)) hasHeavy = true;
  128. }
  129. if (!hasHeavy)
  130. {
  131. vector<int>cur;
  132. int j = i;
  133. while (j != 1 && isHeavy(j, parent[j][0]))
  134. {
  135. assert(block[j] == 0);
  136. cur.push_back(j);
  137. j = parent[j][0];
  138. }
  139. if (cur.size() == 0 || isHeavy(cur.back(), j))
  140. {
  141. assert(block[j] == 0);
  142. cur.push_back(j);
  143. }
  144. blocks[bcnt].init(cur[0], cur.back(), cur.size() + 1);
  145. for (int i = 0; i < cur.size(); i++)
  146. {
  147. int cv = cur[i];
  148. block[cv] = bcnt;
  149. blockpos[cv] = i + 1;
  150. }
  151. bcnt++;
  152. }
  153. }
  154. }
  155. int getLca(int u, int v)
  156. {
  157. if (isAncestor(u, v)) return u;
  158. if (isAncestor(v, u)) return v;
  159. if (u == v) return u;
  160. for (int i = 20; i >= 0; i--)
  161. {
  162. if (!isAncestor(parent[u][i], v))
  163. {
  164. u = parent[u][i];
  165. }
  166. }
  167. return parent[u][0];
  168. }
  169. long long solvePath(int u, int v)
  170. {
  171. int curb = block[u];
  172. long long ans = 0;
  173. while (1)
  174. {
  175. ans = max(ans, blocks[curb].get(u, v));
  176. if (blocks[curb].upv == 1) break;
  177. curb = block[parent[blocks[curb].upv][0]];
  178. }
  179. return ans;
  180. }
  181. long long getMax(int u, int v)
  182. {
  183. int lca = getLca(u, v);
  184. return max(solvePath(u, lca), solvePath(v, lca));
  185. }
  186. void change(int v, int val)
  187. {
  188. blocks[block[v]].change(v, val);
  189. }
  190. int main()
  191. {
  192. //freopen("input.txt", "r", stdin);
  193. //freopen("output.txt", "w", stdout);
  194. int n;
  195. scanf("%d\n", &n);
  196. for (int i = 1; i < n; i++)
  197. {
  198. int u, v;
  199. scanf("%d %d\n", &u, &v);
  200. g[u].push_back(v);
  201. g[v].push_back(u);
  202. }
  203. buildDecomposition(n);
  204. for (int i = 1; i <= n; i++)
  205. {
  206. assert(block[i] != 0);
  207. }
  208. int q;
  209. scanf("%d\n", &q);
  210. for (int i = 1; i <= q; i++)
  211. {
  212. char mode;
  213. scanf("%c ", &mode);
  214. if (mode == 'I')
  215. {
  216. int pos, val;
  217. scanf("%d %d\n", &pos, &val);
  218. change(pos, val);
  219. }
  220. else
  221. {
  222. int u, v;
  223. scanf("%d %d\n", &u, &v);
  224. printf("%lld\n", getMax(u, v));
  225. }
  226. }
  227. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement