Guest User

Untitled

a guest
May 3rd, 2020
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. * code generated by JHelper
  3. * More info: https://github.com/AlexeyDmitriev/JHelper
  4. * @author
  5. */
  6.  
  7. #include <iostream>
  8. #include <fstream>
  9.  
  10. #include <algorithm>
  11. #include <array>
  12. #include <bitset>
  13. #include <cassert>
  14. #include <climits>
  15. #include <cmath>
  16. #include <complex>
  17. #include <cstdio>
  18. #include <cstdlib>
  19. #include <cstring>
  20. #include <functional>
  21. #include <iostream>
  22. #include <map>
  23. #include <memory>
  24. #include <numeric>
  25. #include <queue>
  26. #include <random>
  27. #include <set>
  28. #include <stack>
  29. #include <string>
  30. #include <unordered_map>
  31. #include <vector>
  32.  
  33. #define pb push_back
  34. #define sz(v) ((int)(v).size())
  35. #define all(v) (v).begin(),(v).end()
  36. #define mp make_pair
  37.  
  38. using namespace std;
  39.  
  40. typedef long long int64;
  41. typedef vector<int> vi;
  42. typedef pair<int, int> ii;
  43.  
  44. const int BUBEN = 200;
  45.  
  46. class TaskK {
  47. public:
  48. int n;
  49. int m;
  50. vector<vector<int>> children;
  51. vector<vector<int>> nchildren;
  52. vector<int> depth;
  53. vector<int> right;
  54. vector<int> where;
  55. int dfsOrderPtr;
  56. vector<vector<int>> byDepth;
  57. vector<vector<int>> byDepthFenwick;
  58. //vector<vector<int>> byDepthModulo;
  59. //vector<vector<int>> byDepthModuloFenwick;
  60.  
  61. int dfs(int root, int d) {
  62. int us = dfsOrderPtr++;
  63. depth[us] = d;
  64. where[root] = us;
  65. for (int x : children[root]) {
  66. nchildren[us].push_back(dfs(x, d + 1));
  67. }
  68. right[us] = dfsOrderPtr;
  69. return us;
  70. }
  71.  
  72. void fupd(vector<int>& fenwick, int at, int by) {
  73. while (at < fenwick.size()) {
  74. fenwick[at] += by;
  75. at |= (at + 1);
  76. }
  77. }
  78.  
  79. int fget(const vector<int>& fenwick, int upto) {
  80. int res = 0;
  81. while (upto >= 0) {
  82. res += fenwick[upto];
  83. upto = (upto & (upto + 1)) - 1;
  84. }
  85. return res;
  86. }
  87.  
  88. void solveOne(istream &in, ostream &out) {
  89. in >> n >> m;
  90. children = vector<vector<int>>(n);
  91. for (int i = 1; i < n; ++i) {
  92. int p;
  93. in >> p;
  94. --p;
  95. children[p].push_back(i);
  96. }
  97. depth = vector<int>(n);
  98. where = vector<int>(n);
  99. right = vector<int>(n);
  100. dfsOrderPtr = 0;
  101. nchildren = vector<vector<int>>(n);
  102. dfs(0, 0);
  103. assert(dfsOrderPtr == n);
  104. children = nchildren;
  105.  
  106. byDepth = vector<vector<int>>(n);
  107. for (int i = 0; i < n; ++i) {
  108. byDepth[depth[i]].push_back(i);
  109. }
  110. byDepthFenwick = vector<vector<int>>(n);
  111. for (int i = 0; i < n; ++i) {
  112. byDepthFenwick[i].resize(byDepth[i].size());
  113. }
  114.  
  115. /*byDepthModulo = vector<vector<vector<int>>>(BUBEN);
  116. byDepthModuloFenwick = vector<vector<vector<int>>>(BUBEN);
  117. vector<int> counts;
  118. for (int x = 1; x < BUBEN; ++x) {
  119. counts.clear();
  120. counts.resize(BUBEN, 0);
  121. for (int i = 0; i < n; ++i) {
  122. ++counts[depth[i] % x];
  123. }
  124. byDepthModulo[x].resize(x);
  125. byDepthModuloFenwick[x].resize(x);
  126. for (int i = 0; i < x; ++i) {
  127. byDepthModulo[x][i].reserve(counts[i]);
  128. byDepthModuloFenwick[x][i].resize(counts[i]);
  129. }
  130. for (int i = 0; i < n; ++i) {
  131. byDepthModulo[x][depth[i] % x].push_back(i);
  132. }
  133. for (int i = 0; i < x; ++i) {
  134. assert(byDepthModuloFenwick[x][i].size() == byDepthModulo[x][i].size());
  135. }
  136. }*/
  137.  
  138. vector<int> kinds(m);
  139. vector<int> as(m);
  140. vector<int> xs(m);
  141. vector<int> ys(m);
  142. vector<int> zs(m);
  143. vector<int> results(m);
  144.  
  145. for (int mi = 0; mi < m; ++mi) {
  146. int kind;
  147. in >> kind;
  148. kinds[mi] = kind;
  149. if (kind == 1) {
  150. int a, x, y, z;
  151. in >> a >> x >> y >> z;
  152. --a;
  153. a = where[a];
  154. as[mi] = a;
  155. xs[mi] = x;
  156. ys[mi] = y;
  157. zs[mi] = z;
  158. if (x >= BUBEN) {
  159. for (int d = depth[a] + y; d < n; d += x) {
  160. int from = lower_bound(all(byDepth[d]), a) - byDepth[d].begin();
  161. int to = lower_bound(all(byDepth[d]), right[a]) - byDepth[d].begin();
  162. fupd(byDepthFenwick[d], from, z);
  163. fupd(byDepthFenwick[d], to, -z);
  164. }
  165. }
  166. } else if (kind == 2) {
  167. int a;
  168. in >> a;
  169. --a;
  170. a = where[a];
  171. as[mi] = a;
  172. int res = 0;
  173. int d = depth[a];
  174. int from = lower_bound(all(byDepth[d]), a) - byDepth[d].begin();
  175. res += fget(byDepthFenwick[d], from);
  176. results[mi] = res;
  177. } else {
  178. assert(false);
  179. }
  180. }
  181.  
  182. for (int cx = 1; cx < BUBEN; ++cx) {
  183. byDepth.clear();
  184. byDepth.resize(cx);
  185. for (int i = 0; i < n; ++i) {
  186. byDepth[depth[i] % cx].push_back(i);
  187. }
  188. byDepthFenwick.clear();
  189. byDepthFenwick.resize(cx);
  190. for (int i = 0; i < cx; ++i) {
  191. byDepthFenwick[i].resize(byDepth[i].size());
  192. }
  193. for (int mi = 0; mi < m; ++mi) {
  194. int kind = kinds[mi];
  195. if (kind == 1) {
  196. int a = as[mi];
  197. int x = xs[mi];
  198. int y = ys[mi];
  199. int z = zs[mi];
  200. if (x == cx) {
  201. y = (y + depth[a]) % x;
  202. int from = lower_bound(all(byDepth[y]), a) - byDepth[y].begin();
  203. int to = lower_bound(all(byDepth[y]), right[a]) - byDepth[y].begin();
  204. fupd(byDepthFenwick[y], from, z);
  205. fupd(byDepthFenwick[y], to, -z);
  206. }
  207. } else if (kind == 2) {
  208. int a = as[mi];
  209. int x = cx;
  210. int y = depth[a] % x;
  211. int from = lower_bound(all(byDepth[y]), a) - byDepth[y].begin();
  212. results[mi] += fget(byDepthFenwick[y], from);
  213. } else {
  214. assert(false);
  215. }
  216. }
  217. }
  218.  
  219. for (int mi = 0; mi < m; ++mi) {
  220. if (kinds[mi] == 2) {
  221. out << results[mi] << "\n";
  222. }
  223. }
  224. }
  225.  
  226. void solve(std::istream &in, std::ostream &out) {
  227. int nt;
  228. in >> nt;
  229. for (int it = 0; it < nt; ++it) {
  230. solveOne(in, out);
  231. }
  232. }
  233. };
  234.  
  235.  
  236. int main() {
  237. ios_base::sync_with_stdio(false);
  238. cin.tie(NULL);
  239. TaskK solver;
  240. std::istream& in(std::cin);
  241. std::ostream& out(std::cout);
  242. solver.solve(in, out);
  243. return 0;
  244. }
RAW Paste Data