fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100000 + 10;
  6.  
  7. struct Node {
  8. 	long long add, sum;
  9. };
  10.  
  11. vector<int> G[N];
  12. int a[N], dep[N], fa[N], hson[N], sz[N], top[N], dfn[N], seq[N];
  13. Node sgt[N*4];
  14. int n, m, t;
  15.  
  16. void dfs1(int u, int p) {
  17. 	sz[u] = 1;
  18. 	for (int v: G[u]) {
  19. 		if (v == p) continue;
  20. 		dep[v] = dep[u] + 1;
  21. 		fa[v] = u;
  22. 		dfs1(v, u);
  23. 		sz[u] += sz[v];
  24. 		if (!hson[u] || sz[v] > sz[hson[u]]) hson[u] = v;
  25. 	}
  26. }
  27.  
  28. void dfs2(int u, int p) {
  29. 	dfn[u] = ++ t;
  30. 	seq[t] = a[u];
  31. 	if (!hson[u]) return;
  32. 	top[hson[u]] = top[u];
  33. 	dfs2(hson[u], u);
  34. 	for (int v: G[u]) {
  35. 		if (v == p || v == hson[u]) continue;
  36. 		top[v] = v;
  37. 		dfs2(v, u);
  38. 	}
  39. }
  40.  
  41. void push_down(int index, int begin, int end) {
  42. 	if (sgt[index].add) {
  43. 		int mid = (begin + end) / 2;
  44. 		sgt[index*2].add += sgt[index].add;
  45. 		sgt[index*2].sum += sgt[index].add * (mid - begin + 1);
  46. 		sgt[index*2+1].add += sgt[index].add;
  47. 		sgt[index*2+1].sum += sgt[index].add * (end - mid); 
  48. 		sgt[index].add = 0;
  49. 	}
  50. }
  51.  
  52. void push_up(int index) {
  53. 	sgt[index].sum = sgt[index*2].sum + sgt[index*2+1].sum;
  54. }
  55.  
  56. void build(int index, int begin, int end) {
  57. 	if (begin >= end) {
  58. 		sgt[index].sum = seq[begin];
  59. 		return;
  60. 	}
  61. 	int mid = (begin + end) / 2;
  62. 	build(index * 2, begin, mid);
  63. 	build(index * 2 + 1, mid + 1, end);
  64. 	push_up(index);
  65. }
  66.  
  67. void update(int index, int begin, int end, int left, int right, int val) {
  68. 	if (left <= begin && right >= end) {
  69. 		sgt[index].add += val;
  70. 		sgt[index].sum += 1LL * (end - begin + 1) * val;
  71. 		return;
  72. 	}
  73. 	push_down(index, begin, end);
  74. 	int mid = (begin + end) / 2;
  75. 	if (right <= mid) update(index * 2, begin, mid, left, right, val);
  76. 	else if (left > mid) update(index * 2 + 1, mid + 1, end, left, right, val);
  77. 	else {
  78. 		update(index * 2, begin, mid, left, mid, val);
  79. 		update(index * 2 + 1, mid + 1, end, mid + 1, right, val);
  80. 	}
  81. 	push_up(index);
  82. }
  83.  
  84. long long query(int index, int begin, int end, int left, int right) {
  85. 	if (left <= begin && right >= end) return sgt[index].sum;
  86. 	push_down(index, begin, end);
  87. 	int mid = (begin + end) / 2;
  88. 	if (right <= mid) return query(index * 2, begin, mid, left, right);
  89. 	else if (left > mid) return query(index * 2 + 1, mid + 1, end, left, right);
  90. 	else return query(index * 2, begin, mid, left, mid) + query(index * 2 + 1, mid + 1, end, mid + 1, right);
  91. }
  92.  
  93. long long query(int u) {
  94. 	long long res = query(1, 1, n, dfn[top[u]], dfn[u]);
  95. 	if (top[u] != 1) res += query(fa[top[u]]);
  96. 	return res;
  97. }
  98.  
  99. int main() {
  100. 	int u, v, op, x, w;
  101. 	scanf("%d %d", &n, &m);
  102. 	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
  103. 	for (int i=0; i<n-1; i++) {
  104. 		scanf("%d %d", &u, &v);
  105. 		G[u].push_back(v);
  106. 		G[v].push_back(u);
  107. 	}
  108. 	dfs1(1, -1);
  109. 	top[1] = fa[1] = 1;
  110. 	dfs2(1, -1);
  111. 	build(1, 1, n); 
  112. 	while (m --) {
  113. 		scanf("%d", &op);
  114. 		if (op == 1) {
  115. 			scanf("%d %d", &x, &w);
  116. 			update(1, 1, n, dfn[x], dfn[x], w);
  117. 		}
  118. 		else if (op == 2) {
  119. 			scanf("%d %d", &x, &w);
  120. 			update(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, w);
  121. 		}
  122. 		else {
  123. 			scanf("%d", &x);
  124. 			printf("%lld\n", query(x));
  125. 		}
  126. 	}
  127. 	return 0;
  128. }
Success #stdin #stdout 0.01s 10720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FEi0Dx
language:
C++ (gcc 8.3)
created:
6 days 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!