fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <string>
  10. #include <cstring>
  11. #include <cassert>
  12. #define rf freopen("in.in", "r", stdin)
  13. #define wf freopen("out.out", "w", stdout)
  14. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  15. using namespace std;
  16. const int mx = 1e5 + 10, mod = 1e9+7;
  17. #define mp make_pair
  18. #define pi pair<int, int>
  19. #define ms(a, v) memset(a, int(v), sizeof(a))
  20.  
  21. static int C[mx], A, B, P;
  22. int n, t, q, qs, qe, val, chno=1, idx=0;
  23. int neg_inf = -2e9;
  24.  
  25. static int pos[mx], wc[mx], chain[mx], leaf_val[mx],
  26.            l[mx], lca[mx][20], ch[mx], vis[mx], p[mx];
  27.  
  28. struct node
  29. {
  30. 	int max_alive, number_alive, lazy_update_val;
  31. } st[mx*4];
  32.  
  33. vector<int> g[mx];
  34. int cmp(int l, int r)
  35. {
  36. 	return ch[l]>ch[r];
  37. }
  38.  
  39. /*----------Segment tree functions-----------*/
  40.  
  41. void merge(int r)
  42. {
  43. 	st[r].number_alive = st[2*r].number_alive + st[2*r+1].number_alive;
  44. 	st[r].max_alive = max(st[2*r].max_alive, st[2*r+1].max_alive) + st[r].lazy_update_val;
  45. } 
  46.  
  47. void build(int x, int y, int r)
  48. {
  49. 	if(x == y)
  50. 	{
  51. 		st[r].max_alive = leaf_val[x];
  52. 		st[r].lazy_update_val = 0;
  53. 		st[r].number_alive = (leaf_val[x] < P);
  54. 		return;
  55. 	}
  56.  
  57. 	int m = (x+y) >> 1;
  58. 	st[r].lazy_update_val = 0;
  59. 	build(x, m, 2*r); build(m+1, y, 2*r+1);
  60.  
  61. 	merge(r);	
  62. }
  63. void up(int x, int y, int r)
  64. {
  65. 	if(y<qs or qe<x or qs>qe)
  66. 		return;
  67.  
  68. 	if(qs<=x && y<=qe)
  69. 	{
  70. 		st[r].lazy_update_val += val, st[r].max_alive += val;
  71. 		return;
  72. 	}
  73.  
  74. 	int m=(x+y)>>1;
  75. 	up(x, m, 2*r); up(m+1, y, 2*r+1);
  76.  
  77. 	merge(r);
  78. }
  79.  
  80. void propagate(int x, int y, int r, int lazy)
  81. {
  82. 	if(st[r].max_alive + lazy < P or !st[r].number_alive)
  83. 	{
  84. 		st[r].max_alive += lazy;
  85. 		st[r].lazy_update_val += lazy;
  86. 		return;
  87. 	}
  88.  
  89. 	if(x==y)
  90. 	{
  91. 		if(st[r].max_alive + lazy >= P)
  92. 			st[r].max_alive = neg_inf, st[r].number_alive = 0;
  93. 		return;
  94. 	}
  95.  
  96. 	int m = (x+y)>>1;
  97. 	lazy += st[r].lazy_update_val;
  98. 	st[r].lazy_update_val = 0;
  99.  
  100. 	propagate(x, m, 2*r, lazy); propagate(m+1, y, 2*r+1, lazy);
  101. 	merge(r);
  102. }
  103.  
  104. int qu(int x, int y, int r, int lazy)
  105. {
  106. 	st[r].max_alive += lazy;
  107. 	st[r].lazy_update_val += lazy;
  108.  
  109. 	if(y<qs || qe<x || qs>qe)
  110. 		return 0;
  111.  
  112. 	if(qs<=x && y<=qe)
  113. 	{
  114. 		propagate(x, y, r, 0);
  115. 		return (y-x+1) - st[r].number_alive;
  116. 	}
  117.  
  118. 	int m = (x+y)>>1;
  119. 	lazy = st[r].lazy_update_val;
  120. 	st[r].lazy_update_val = 0;
  121.  
  122. 	int ret = qu(x, m, 2*r, lazy) + qu(m+1, y, 2*r+1, lazy);
  123. 	merge(r);
  124.  
  125. 	return ret;
  126. }
  127. /*-----------------------------------------*/
  128.  
  129. /*-----------Lowest Common Ancestor---------*/
  130. int lcanc(int x, int y)
  131. {
  132. 	if(l[x]<l[y]) swap(x, y);
  133. 	while(l[x]>l[y])
  134. 	{
  135. 		int j=log2(l[x]-l[y]);
  136. 		x=lca[x][j];
  137. 	}
  138.  
  139. 	int j=log2(l[x]);
  140. 	while(x!=y)
  141. 	{
  142. 		while(lca[x][j]==lca[y][j] && j)
  143. 			j--;
  144. 		x=lca[x][j], y=lca[y][j];
  145. 	}
  146. 	return x;
  147. }
  148. /*-----------------------------------------*/
  149.  
  150. /*-----------DFS to Preprocess---------*/
  151. void dfs(int u)
  152. {
  153. 	vis[u]=ch[u]=1;
  154. 	rep(i, 0, g[u].size()-1)
  155. 	{
  156. 		int v=g[u][i];
  157. 		if(vis[v]) continue;
  158.  
  159. 		l[v]=l[u]+1;
  160. 		p[v]=lca[v][0]=u;
  161.  
  162. 		int go=u, j=1;
  163. 		while(go!=-1)
  164. 		{
  165. 			go=lca[v][j]=lca[go][j-1];
  166. 			j++;
  167. 		}
  168.  
  169. 		dfs(v);
  170. 		ch[u]+=ch[v];
  171. 	}
  172. }
  173. /*----------------------------------------------*/
  174.  
  175. /*------------Heavy Light Decomposition---------*/
  176.  
  177. void hld(int u)
  178. {
  179. 	wc[u]=chno;
  180. 	pos[u]=++idx; leaf_val[idx] = C[u];
  181.  
  182. 	for(int i=1; i<g[u].size(); ++i)
  183. 	{
  184. 		int v=g[u][i];
  185. 		if(i==1)
  186. 		{
  187. 			hld(v);
  188. 			continue;
  189. 		}
  190.  
  191. 		chno++;
  192. 		chain[chno]=v;
  193. 		hld(v);
  194. 	}
  195. }
  196. /*------------------------------------------------*/
  197.  
  198. /*---------- UPDATE AND QUERY FUNCTIONS-----------*/
  199.  
  200. int updater(int a, int b, int chk)
  201. {
  202. 	int ret=0;
  203. 	while(true)
  204. 	{
  205. 		if(wc[a]==wc[b])
  206. 		{
  207. 			qs=pos[b]+chk, qe=pos[a];
  208. 			up(1, n, 1);
  209. 			break;
  210. 		}
  211.  
  212. 		int chnh=chain[wc[a]];
  213.  
  214. 		qs=pos[chnh], qe=pos[a];
  215. 		up(1, n, 1);
  216.  
  217. 		a=p[chnh];
  218. 	}
  219. 	return ret;
  220. }
  221. void update(int u, int v, int w)
  222. {
  223. 	val = w;
  224. 	int anc = lcanc(u, v);
  225. 	updater(u, anc, 0); updater(v, anc, 1);
  226. }
  227.  
  228. int getans(int a, int b, int chk)
  229. {
  230. 	int ret=0;
  231. 	while(1)
  232. 	{
  233. 		if(wc[a]==wc[b])
  234. 		{
  235. 			qs=pos[b]+chk, qe=pos[a];
  236. 			ret += qu(1, n, 1, 0);
  237. 			break;
  238. 		}
  239.  
  240. 		int chnh=chain[wc[a]];
  241.  
  242. 		qs=pos[chnh], qe=pos[a];
  243. 		ret += qu(1, n, 1, 0);
  244.  
  245. 		a=p[chnh];
  246. 	}
  247.  
  248. 	return ret;
  249. }
  250. int query(int u, int v)
  251. {
  252. 	int anc = lcanc(u, v);
  253. 	return getans(u, anc, 0) + getans(v, anc, 1);
  254. }
  255. /*----------------------------------------------*/
  256.  
  257. int main()
  258. {
  259. 	//rf; wf;
  260.  
  261. 	scanf("%d", &t);
  262. 	while(t--)
  263. 	{
  264. 		scanf("%d %d %d %d", &n, &q, &A, &B);
  265. 		if(A == 0)
  266. 			P = (B>=0)? neg_inf: -1*neg_inf;
  267. 		else
  268. 			P = (B < 0)? ceil((-1.0*B)/A): (-B)/A;
  269.  
  270. 		rep(i, 0, n)
  271. 		{
  272. 			g[i].clear(), vis[i]=0, ch[i]=0;
  273. 			rep(j, 0, 19)
  274. 				lca[i][j]=-1;
  275. 		}
  276. 		g[1].push_back(0);
  277. 		vis[0]=1, ch[0]=1e9;
  278.  
  279. 		rep(i, 1, n)
  280. 			scanf("%d", &C[i]);
  281. 		rep(i, 1, n-1)
  282. 		{
  283. 			int u, v;
  284. 			scanf("%d %d", &u, &v);
  285.  
  286. 			g[u].push_back(v);
  287. 			g[v].push_back(u);
  288. 		}
  289.  
  290. 		dfs(1);
  291. 		rep(i, 1, n)
  292. 			sort(g[i].begin(), g[i].end(), cmp);
  293.  
  294. 		chno=1, idx=0; chain[1]=1;
  295. 		hld(1);
  296. 		build(1, n, 1);
  297.  
  298. 		while(q--)
  299. 		{
  300. 			int type, u, v, w;
  301. 			scanf("%d %d %d", &type, &u, &v);
  302.  
  303. 			if(type == 1)
  304. 				scanf("%d", &w),
  305. 				update(u, v, w);
  306. 			else
  307. 				printf("%d\n", query(u, v));
  308. 		}
  309. 	}
  310. 	return 0;
  311. }
Success #stdin #stdout 0s 20616KB
comments (?)
stdin
copy 
1
5 6
1 0
-1 2 -3 4 -5
1 2
1 3
2 4
2 5
1 4 3 1
2 4 3
1 3 3 1
2 3 3
1 3 3 2
2 4 3
stdout
copy 
3
0
4
https://ideone.com/w6yY8F
language:
C++ (gcc 8.3)
created:
8 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!