fork download
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <limits>
  5. #include <iostream>
  6. #include <vector>
  7. #include <cassert>
  8. #include <complex>
  9. #include <cstring>
  10. #include <map>
  11. #include <cmath>
  12. #include <set>
  13. #include <algorithm>
  14. #include <queue>
  15.  
  16. using namespace std;
  17. typedef long long Long;
  18.  
  19. typedef vector<int> VI;
  20. typedef vector<Long> VL;
  21. typedef vector<VI> VVI;
  22. struct FragmentedTree {
  23. VVI adj;
  24. VVI adj2;
  25. int N, SQ;
  26. VI L, P, G, SZ;
  27. VL V;
  28. struct Fragment {
  29. int u, p,maxL, N;
  30. VI nodes, &L;
  31. VI lvlFrec;
  32. Long tot;
  33. VL &V;
  34. Fragment(int u, int N, VL &V, VI &L):u(u),N(N),V(V),L(L){
  35. p = -1;
  36. tot = 0;
  37. maxL = -1;
  38. }
  39. void add(int v){
  40. int nl = L[v] - L[u];
  41. nodes.push_back(v);
  42. if(v >= N)return;
  43. if(nl > maxL){
  44. maxL = nl;
  45. lvlFrec.resize(maxL+1);
  46. }
  47. lvlFrec[nl]++;
  48. }
  49. void update(int lvl, Long v){
  50. int nl = lvl - L[u];
  51. if(nl < 0 || nl > maxL)return;
  52. tot += v * lvlFrec[nl];
  53. }
  54. Long query(){
  55. return tot;
  56. }
  57. };
  58. vector<Fragment> frags;
  59. FragmentedTree(int N):N(N),adj(N),P(N,-1),L(N),G(N,-1),V(N),SZ(N){
  60. SQ = max((int)sqrt(N),2);
  61. }
  62. void addEdge(int u,int v){
  63. adj[u].push_back(v);
  64. }
  65. // G : fragment u belongs
  66. // frags : all fragments
  67. // leader() : returns the leader of the fragment
  68. // query() : query on a fragment (ideally O(1))
  69. // pushDown(): update all the values in the fragment
  70. // adj : adjacencyList
  71. // adj2 : subAdjacencyList
  72. Long getSum(int u){
  73. if(leader(u) == u){
  74. Long w = frags[ G[u] ].query();
  75. for(int g : adj2[ G[u] ]){
  76. w += getSum( frags[g].u );
  77. }
  78. return w;
  79. }else{
  80. Long w = V[ L[u] ];
  81. for(int v : adj[u]){
  82. w += getSum(v);
  83. }
  84. return w;
  85. }
  86. }
  87. void update(int LVL, Long v){
  88. V[LVL] += v;
  89. for(Fragment &f : frags){
  90. f.update(LVL, v);
  91. }
  92. }
  93. int createNode(int u, VI nex){
  94. G.push_back(-1);
  95. P.push_back(u);
  96. L.push_back(u <= 0 ? 0 : L[u]+1);
  97. int nn = adj.size();
  98. adj.push_back(nex);
  99. return nn;
  100. }
  101. void dfsL(int u, int LVL = 0){
  102. L[u] = LVL;
  103. SZ[u] = 1;
  104. for(int v : adj[u]){
  105. dfsL(v, LVL+1);
  106. SZ[u] += SZ[v];
  107. }
  108. }
  109. void buildFragment(int u, Fragment &F){
  110. if(G[u] != -1)return;
  111. G[u] = frags.size() - 1;
  112. F.add(u);
  113. for(int v : adj[u]){
  114. buildFragment(v, F);
  115. }
  116. }
  117. void fragment(){
  118. dfsL(0);
  119. VVI nodesByLevel(N);
  120. for(int i = 0; i < N; ++i)
  121. nodesByLevel[ N-1-L[i] ].push_back(i);
  122. for(VI p : nodesByLevel){
  123. for(int u : p){
  124. vector<int> toF;
  125. VI temp, child = adj[u], spChild;
  126. int sz = 0;
  127. SZ[u] = 1;
  128. for(int v : child){
  129. SZ[u] += SZ[v];
  130. }
  131. for(int v : child){
  132. sz += SZ[v];
  133. temp.push_back(v);
  134. if(sz > SQ){
  135. int nn = createNode(u, temp);
  136. temp.clear();
  137. spChild.push_back(nn);
  138. frags.push_back(Fragment(nn, N, V, L));
  139. buildFragment(nn, frags.back());
  140. SZ[u] -= sz;
  141. sz = 0;
  142. }
  143. }
  144. adj[u] = temp;
  145. for(int v : spChild)
  146. adj[u].push_back(v);
  147. }
  148. }
  149. int nn = createNode(-1, VI(1,0));
  150. frags.push_back(Fragment(nn, N, V, L));
  151. buildFragment(nn, frags.back());
  152. adj2 = VVI(frags.size());
  153. for(int i = 0; i < frags.size(); ++i){
  154. Fragment &f = frags[i];
  155. if(P[f.u] == -1)continue;
  156. f.p = G[ P[f.u] ];
  157. adj2[ f.p ].push_back(i);
  158. }
  159. }
  160. int leader(int u){
  161. return frags[G[u]].u;
  162. }
  163. int lca(int u,int v){
  164. while(leader(u) != leader(v)){
  165. if(L[ leader(u) ] > L[ leader(v)]){
  166. u = P[ leader(u) ];
  167. }else{
  168. v = P[ leader(v) ];
  169. }
  170. }
  171. while(u != v){
  172.  
  173. if(L[v] > L[u]){
  174. v = P[v];
  175. }else{
  176. u = P[u];
  177. }
  178. }
  179. return u;
  180. }
  181. };
  182.  
  183. int main(){
  184.  
  185. int N,M;
  186. scanf("%d%d", &N, &M);
  187. int fu = -1, fv = -1;
  188. FragmentedTree FT(N);
  189. for(int i = 0; i < N-1; ++i){
  190. int u,v;
  191. scanf("%d%d", &u, &v);
  192. // u = i+1;
  193. // v = i+2;
  194. u--;v--;
  195. if(fu == -1){
  196. fu = u;
  197. fv = v;
  198. }
  199. FT.addEdge(u,v);
  200. }
  201. FT.fragment();
  202. // for(FragmentedTree::Fragment f : FT.frags){
  203. // for(int u : f.nodes){
  204. // cout << u << " ";
  205. // }
  206. // cout << endl;
  207. // }
  208. // for(FragmentedTree::Fragment f : FT.frags){
  209. // cout << f.p << endl;
  210. // }
  211. // return 0;
  212. // if(fu == 0 && fv == 1 && N == 20000){
  213. // cout << FT.frags.size() << endl;
  214. // }
  215. for(int i = 0; i < M; ++i){
  216.  
  217.  
  218. int c;
  219. scanf("%d", &c);
  220. // c = rand() % 2+1;
  221. if(c == 1){
  222. int L,Y;
  223. scanf("%d%d", &L, &Y);
  224. // L = rand() % 2;
  225. // Y = rand() % 1000000000 + 1;
  226. FT.update(L, Y);
  227. }else{
  228. int X;
  229. scanf("%d", &X);
  230. // X = rand() % N + 1;
  231. X--;
  232. // if(fu == 0 && fv == 10913){
  233. //// cout << i << endl;
  234. // }else{
  235. cout << FT.getSum(X) << endl;
  236. // }
  237. }
  238. }
  239.  
  240. }
  241.  
  242.  
  243. /*
  244.  
  245. 5 4
  246. 1 2
  247. 1 3
  248. 3 4
  249. 3 5
  250. 1 1 2
  251. 1 2 3
  252. 2 3
  253. 2 1
  254.  
  255.  0
  256. 1 2
  257.   3 4
  258.  */
Success #stdin #stdout 0s 4348KB
stdin
5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1
stdout
8
10