Advertisement
josdas

Untitled

Jun 5th, 2017
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.66 KB | None | 0 0
  1. #define _ijps 0
  2. #define _ALLOW_RTCc_IN_STL
  3. #define _CRT_SECURE_NO_DEPRECATE
  4. //#pragma comment(linker, "/STACK:667772160")
  5. #include <iostream>
  6. #include <cmath>
  7. #include <vector>
  8. #include <time.h>
  9. #include <map>
  10. #include <set>
  11. #include <deque>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <unordered_map>
  15. #include <unordered_set>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <string>
  19. #include <fstream>
  20. #include <assert.h>
  21. #include <list>
  22. #include <cstring>
  23. #include <queue>
  24. using namespace std;
  25.  
  26. #define name "treepathadd"
  27.  
  28. typedef long long ll;
  29.  
  30. struct __isoff {
  31. __isoff() {
  32. if(_ijps)
  33. freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);//, freopen("test.txt", "w", stderr);
  34. else freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);
  35. //ios_bsume::sync_with_stdio(0);
  36. //srand(time(0));
  37. srand('C' + 'T' + 'A' + 'C' + 'Y' + 'M' + 'B' + 'A');
  38. }
  39. ~__isoff() {
  40. //if(_ijps) cout<<times<<'\n';
  41. }
  42. } __osafwf;
  43.  
  44. const ll inf = (ll)2e18;
  45. const int dd = (int)6e5 + 5;
  46. const int super = 2123123;
  47. ll T[dd * 4];
  48. ll A[dd * 4];
  49. ll S[dd * 4];
  50.  
  51. void build(int v, int l, int r, vector<ll> const& P) {
  52. S[v] = super;
  53. if(l == r) {
  54. T[v] = P[l];
  55. return;
  56. }
  57. int s = (l + r) / 2;
  58. build(v * 2, l, s, P);
  59. build(v * 2 + 1, s + 1, r, P);
  60. T[v] = T[v * 2] + T[v * 2 + 1];
  61. }
  62.  
  63. void sset(int v, int l, int r, int lq, int rq, ll x) {
  64. if(lq > rq) {
  65. return;
  66. }
  67. if(l == lq && r == rq) {
  68. T[v] += x;
  69. return;
  70. }
  71. int s = (l + r) / 2;
  72. sset(v * 2, l, s, lq, min(rq, s), x);
  73. sset(v * 2 + 1, s + 1, r, max(lq, s + 1), rq, x);
  74. T[v] = T[v * 2] + T[v * 2 + 1];
  75. }
  76.  
  77. ll get(int v, int l, int r, int lq, int rq) {
  78. if(lq > rq) {
  79. return 0;
  80. }
  81. if(l == lq && r == rq) {
  82. return T[v];
  83. }
  84. int s = (l + r) / 2;
  85. return get(v * 2, l, s, lq, min(rq, s)) +
  86. get(v * 2 + 1, s + 1, r, max(lq, s + 1), rq);
  87. }
  88.  
  89.  
  90. const int Df = 20;
  91. vector<int> P[dd];
  92. int Lca[Df][dd];
  93. int H[dd], L[dd], R[dd], tt;
  94.  
  95. void dfs(int v, int p, int h) {
  96. L[v] = tt++;
  97. H[v] = h;
  98. Lca[0][v] = p;
  99. for(int i = 1; i < Df; i++) {
  100. Lca[i][v] = Lca[i - 1][Lca[i - 1][v]];
  101. }
  102. for(auto u : P[v]) {
  103. if(u != p) {
  104. dfs(u, v, h + 1);
  105. }
  106. }
  107. R[v] = tt++;
  108. }
  109.  
  110. bool is(int a, int b) {
  111. return L[a] <= L[b] && R[b] <= R[a];
  112. }
  113.  
  114. int lca(int a, int b) {
  115. if(is(a, b)) {
  116. return a;
  117. }
  118. if(is(b, a)) {
  119. return b;
  120. }
  121. for(int i = Df - 1; i >= 0; i--) {
  122. int c = Lca[i][a];
  123. if(!is(c, b)) {
  124. a = c;
  125. }
  126. }
  127. return Lca[0][a];
  128. }
  129.  
  130. void add_p(int v, int x) {
  131. sset(1, 0, dd - 1, L[v], L[v], x);
  132. }
  133.  
  134. void add_p(int a, int b, int x) {
  135. int c = lca(a, b);
  136. add_p(a, x);
  137. add_p(b, x);
  138. add_p(c, -x);
  139. if(c > 0) {
  140. add_p(Lca[0][c], -x);
  141. }
  142.  
  143. }
  144.  
  145. int main() {
  146. ios_base::sync_with_stdio(0);
  147. int n;
  148. cin >> n;
  149. for(int i = 0; i < n - 1; i++) {
  150. int a, b;
  151. cin >> a >> b;
  152. a--, b--;
  153. P[a].push_back(b);
  154. P[b].push_back(a);
  155. }
  156. dfs(0, 0, 0);
  157. int m;
  158. cin >> m;
  159. for(int i = 0; i < m; i++) {
  160. char c;
  161. cin >> c;
  162. if(c == '+') {
  163. int a, b, x;
  164. cin >> a >> b >> x;
  165. a--, b--;
  166. add_p(a, b, x);
  167. }
  168. else {
  169. int a;
  170. cin >> a;
  171. a--;
  172. cout << get(1, 0, dd - 1, L[a], R[a]) << '\n';
  173. }
  174. }
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement