fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace cartesian {
  6.  
  7. 	struct node;
  8. 	typedef node* treap;
  9.  
  10. 	struct node {
  11. 		node *l = 0, *r = 0, *p = 0;
  12. 		int64_t sum = 0, to_add = 0, val = 0;
  13. 		int to_nul = 0, siz = 1;
  14. 		int key, prior;
  15.  
  16. 		node(int key, int val): sum(val), val(val), key(key), prior(rand()) {}
  17.  
  18.  
  19. 		#define safe(x, op) (x ? x->op : 0)
  20.  
  21. 		treap fix() {
  22. 			safe(l, p = this);
  23. 			safe(r, p = this);
  24. 			sum = val + safe(l, sum) + safe(r, sum);
  25. 			siz = 1 + safe(l, siz) + safe(r, siz);
  26. 			return this;
  27. 		}
  28. 		treap cut_l() {
  29. 			push();
  30. 			safe(l, p = 0);
  31. 			return l;
  32. 		}
  33. 		treap cut_r() {
  34. 			push();
  35. 			safe(r, p = 0);
  36. 			return r;
  37. 		}
  38. 		treap set_l(treap x) {
  39. 			l = x;
  40. 			return fix();
  41. 		}
  42. 		treap set_r(treap x) {
  43. 			r = x;
  44. 			return fix();
  45. 		}
  46.  
  47. 		treap nullify() {
  48. 			to_nul = 1;
  49. 			sum = to_add = val = 0;
  50. 			return this;
  51. 		}
  52. 		treap add(int64_t k) {
  53. 			to_add += k;
  54. 			val += k;
  55. 			sum += siz * k;
  56. 			return this;
  57. 		}
  58.  
  59. 		treap push() {
  60. 			if(to_nul) {
  61. 				safe(l, nullify());
  62. 				safe(r, nullify());
  63. 				to_nul = 0;
  64. 			}
  65. 			if(to_add) {
  66. 				safe(l, add(to_add));
  67. 				safe(r, add(to_add));
  68. 				to_add = 0;
  69. 			}
  70. 			return this;
  71. 		}		
  72. 		treap root() {
  73. 			return p ? p->root() : this;
  74. 		}
  75. 		treap min() {
  76. 			return l ? l->min() : this;
  77. 		}
  78. 	};
  79. 	treap merge(treap a, treap b) {
  80. 		if(!a || !b) {
  81. 			return a ? a : b;
  82. 		} else if(a->prior < b->prior) {
  83. 			return a->set_r(merge(a->cut_r(), b));
  84. 		} else {
  85. 			return b->set_l(merge(a, b->cut_l()));
  86. 		}
  87. 	}
  88. 	pair<treap, treap> split(treap a, int k) {
  89. 		treap b, c;
  90. 		if(!a) {
  91. 			return {0, 0};
  92. 		} else if(a->key < k) {
  93. 			tie(b, c) = split(a->cut_r(), k);
  94. 			return {a->set_r(b), c};
  95. 		} else {
  96. 			tie(b, c) = split(a->cut_l(), k);
  97. 			return {b, a->set_l(c)};
  98. 		}
  99. 	}
  100. 	pair<treap, treap> cut(treap a, int l, int r) {
  101. 		treap b, c;
  102. 		tie(a, b) = split(a, l);
  103. 		tie(b, c) = split(b, r);
  104. 		return {merge(a, c), b};
  105. 	}
  106. 	treap link(treap a, treap x) {
  107. 		treap b;
  108. 		tie(a, b) = split(a, x->min()->key);
  109. 		return merge(a, merge(x, b));
  110. 	}
  111. 	pair<treap, treap> cut(treap x) {
  112. 		return cut(x->root(), x->key, x->key + 1);
  113. 	}
  114. };
  115.  
  116. using namespace cartesian;
  117.  
  118. const int maxn = 5e5 + 42;
  119.  
  120. int to[maxn], a[maxn], in[maxn], out[maxn], par[maxn];
  121. vector<int> g[maxn];
  122. int sz, t;
  123. string s;
  124.  
  125. treap nod[maxn];
  126.  
  127. void dfs(int v = 0, int p = 0) {
  128. 	in[v] = t++;
  129. 	nod[v] = new node(in[v], a[v]);
  130. 	for(auto it: g[v]) {
  131. 		int u = to[it];
  132. 		if(u != p) {
  133. 			par[u] = v;
  134. 			dfs(u, v);
  135. 			if(s[it / 2] == '0') {
  136. 				merge(nod[v]->root(), nod[u]->root());
  137. 			}
  138. 		}
  139. 	}
  140. 	out[v] = t;
  141. }
  142.  
  143. void inv(int u, int v) {
  144. 	if(in[u] > in[v]) {
  145. 		swap(u, v);
  146. 	}
  147. 	auto U = nod[u]->root();
  148. 	auto V = nod[v]->root();
  149. 	if(U != V) {
  150. 		link(U, V);
  151. 	} else {
  152. 		cut(U, in[v], out[v]);
  153. 	}
  154. }
  155. void add(int x, int c) {
  156. 	nod[x]->root()->add(c);
  157. }
  158. void compose(int x) {
  159. 	treap a, b;
  160. 	tie(a, b) = cut(nod[x]);
  161. 	b->add(safe(a, sum));
  162. 	safe(a, nullify());
  163. 	link(a, b);
  164. }
  165. int64_t get(int x) {
  166. 	treap a, b;
  167. 	tie(a, b) = cut(nod[x]);
  168. 	int64_t res = b->sum;
  169. 	link(a, b);
  170. 	return res;
  171. }
  172. int64_t get_total(int x) {
  173. 	return nod[x]->root()->sum;
  174. }
  175. void full_nul(int x) {
  176. 	nod[x]->root()->nullify();
  177. }
  178.  
  179.  
  180. signed main() {
  181. 	//freopen("input.txt", "r", stdin);
  182. 	ios::sync_with_stdio(0);
  183. 	cin.tie(0);
  184. 	int n, m;
  185. 	cin >> n;
  186. 	cin >> n >> m;
  187. 	int u[n], v[n];
  188. 	for(int i = 0; i < n - 1; i++) {
  189. 		cin >> u[i] >> v[i];
  190. 		u[i]--, v[i]--;
  191. 		g[v[i]].push_back(sz);
  192. 		to[sz++] = u[i];
  193. 		g[u[i]].push_back(sz);
  194. 		to[sz++] = v[i];
  195. 	}
  196. 	cin >> s;
  197. 	for(int i = 0; i < n; i++) {
  198. 		cin >> a[i];
  199. 	}
  200. 	dfs();
  201. 	for(int i = 0; i < m; i++) {
  202. 		int t;
  203. 		cin >> t;
  204. 		if(t == 1) {
  205. 			int i;
  206. 			cin >> i;
  207. 			inv(u[i - 1], v[i - 1]);
  208. 		} else if(t == 2) {
  209. 			int x, c;
  210. 			cin >> x >> c;
  211. 			add(x - 1, c);
  212. 		} else if(t == 3) {
  213. 			int x;
  214. 			cin >> x;
  215. 			compose(x - 1);
  216. 		} else if(t == 4) {
  217. 			int x;
  218. 			cin >> x;
  219. 			cout << get(x - 1) << endl;
  220. 		} else if(t == 5) {
  221. 			int x;
  222. 			cin >> x;
  223. 			cout << get_total(x - 1) << endl;
  224. 		} else if(t == 6) {
  225. 			int x;
  226. 			cin >> x;
  227. 			full_nul(x - 1);
  228. 		} else {
  229. 			cout << 0 << endl;
  230. 		}
  231. 	}
  232. 	return 0;
  233. }
Success #stdin #stdout 0s 40632KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/v7BLN4
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!