fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstdio>
  5. #include <algorithm>
  6. using namespace std;
  7. const int inf = 2e5 + 9;
  8. typedef long long ll;
  9. #define le x+x
  10. #define ri x+x+1
  11. #define mid (l+r)/2
  12. int timer = 0;
  13. int beg[inf];
  14. int en[inf];
  15. vector<int>adj[inf];
  16. ll sgt[inf << 2];
  17. void dfs(int x, int p) {
  18. 	beg[x] = timer++;
  19. 	for (auto &k : adj[x]) {
  20. 		if (k != p)
  21. 			dfs(k, x);
  22. 	}
  23. 	en[x] = timer - 1;
  24. }
  25. int s, e, v;
  26. void update(int x, int l, int r) {
  27. 	if (s <= l && e >= r) {
  28. 		sgt[x] += v;
  29. 		return;
  30. 	}
  31. 	if (mid >= s)
  32. 		update(le, l, mid);
  33. 	if (mid + 1 <= e)
  34. 		update(ri, mid + 1, r);
  35. }
  36. ll query(int x, int l, int r) {
  37. 	if (l == r)
  38. 		return sgt[x];
  39. 	if (mid >= s)
  40. 		return sgt[x] + query(le, l, mid);
  41. 	return sgt[x] + query(ri, mid + 1, r);
  42. }
  43. int source[inf];
  44. ll accVal[inf];
  45. int main() {
  46. 	int n, m, q;
  47. 	int a, b, c;
  48. 	scanf("%d%d%d", &n, &m, &q);
  49. 	for (int i = 0; i < n; ++i) {
  50. 		scanf("%d", &a);
  51. 		source[i] = a - 1;//-1
  52. 	}
  53. 	for (int i = 1; i < m; ++i) {
  54. 		scanf("%d", &a);
  55. 		--a;
  56. 		adj[i].push_back(a);
  57. 		adj[a].push_back(i);
  58. 	}
  59. 	dfs(0, -1);
  60. 	while (q--) {
  61. 		scanf("%d", &a);
  62. 		if (a == 1) {
  63. 			scanf("%d%d", &b, &v);
  64. 			--b;
  65. 			s = beg[b];
  66. 			e = en[b];
  67. 			if (s > e)exit(-1);
  68. 			update(1, 0, m - 1);
  69. 		}
  70. 		else if (a == 2) {
  71. 			scanf("%d%d", &b,&c);	
  72. 			--b;
  73. 			--c;
  74. 			int reg = source[b];
  75. 			s = beg[reg];
  76. 			ll res=query(1, 0, m - 1);
  77. 			accVal[b] += res;
  78. 			// determine the amount in the transferred one
  79. 			s = beg[c];
  80. 			res = query(1, 0, m - 1);
  81. 			accVal[b] -= res;
  82. 			source[b] = c;
  83. 		}
  84. 		else if (a == 3) {
  85. 			scanf("%d", &b);
  86. 			--b;
  87. 			int reg = source[b];
  88. 			s = beg[reg];
  89. 			ll res = query(1, 0, m - 1);
  90. 			printf("%lld\n", accVal[b] + res);
  91. 		}
  92. 	}
  93.  
  94. }
  95.  
Success #stdin #stdout 0s 30080KB
comments (?)
stdin
copy 
6 5 5 
1 2 3 4 4 5
1 1 3 3 
1 3 2 
2 5 2 
3 2 
1 2 1 
3 5
stdout
copy 
0
3
https://ideone.com/701deJ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!