fork(20) download
copy 
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <limits>
  5. #include <iostream>
  6. #include <vector>
  7. #include <cassert>
  8. #include <complex>
  9. #include <cstring>
  10. #include <map>
  11. #include <cmath>
  12. #include <set>
  13. #include <algorithm>
  14. #include <queue>
  15.  
  16. using namespace std;
  17. typedef long long Long;
  18.  
  19. typedef vector<int> VI;
  20. typedef vector<Long> VL;
  21. typedef vector<VI> VVI;
  22. struct FragmentedTree {
  23. 	VVI adj;
  24. 	VVI adj2;
  25. 	int N, SQ;
  26. 	VI L, P, G, SZ;
  27. 	VL V;
  28. 	struct Fragment {
  29. 		int u, p,maxL, N;
  30. 		VI nodes, &L;
  31. 		VI lvlFrec;
  32. 		Long tot;
  33. 		VL &V;
  34. 		Fragment(int u, int N, VL &V, VI &L):u(u),N(N),V(V),L(L){
  35. 			p = -1;
  36. 			tot  = 0;
  37. 			maxL = -1;
  38. 		}
  39. 		void add(int v){
  40. 			int nl = L[v] - L[u];
  41. 			nodes.push_back(v);
  42. 			if(v >= N)return;
  43. 			if(nl > maxL){
  44. 				maxL = nl;
  45. 				lvlFrec.resize(maxL+1);
  46. 			}
  47. 			lvlFrec[nl]++;
  48. 		}
  49. 		void update(int lvl, Long v){
  50. 			int nl = lvl - L[u];
  51. 			if(nl < 0 || nl > maxL)return;
  52. 			tot += v * lvlFrec[nl];
  53. 		}
  54. 		Long query(){
  55. 			return tot;
  56. 		}
  57. 	};
  58. 	vector<Fragment> frags;
  59. 	FragmentedTree(int N):N(N),adj(N),P(N,-1),L(N),G(N,-1),V(N),SZ(N){
  60. 		SQ = max((int)sqrt(N),2);
  61. 	}
  62. 	void addEdge(int u,int v){
  63. 		adj[u].push_back(v);
  64. 	}
  65. 	// G         : fragment u belongs
  66. 	// frags     : all fragments
  67. 	// leader()  : returns the leader of the fragment
  68. 	// query()   : query on a fragment (ideally O(1))
  69. 	// pushDown(): update all the values in the fragment
  70. 	// adj       : adjacencyList
  71. 	// adj2		 : subAdjacencyList
  72. 	Long getSum(int u){
  73. 		if(leader(u) == u){
  74. 			Long w = frags[ G[u] ].query();
  75. 			for(int g : adj2[ G[u] ]){
  76. 				w += getSum( frags[g].u );
  77. 			}
  78. 			return w;
  79. 		}else{
  80. 			Long w = V[ L[u] ];
  81. 			for(int v : adj[u]){
  82. 				w += getSum(v);
  83. 			}
  84. 			return w;
  85. 		}
  86. 	}
  87. 	void update(int LVL, Long v){
  88. 		V[LVL] += v;
  89. 		for(Fragment &f : frags){
  90. 			f.update(LVL, v);
  91. 		}
  92. 	}
  93. 	int createNode(int u, VI nex){
  94. 		G.push_back(-1);
  95. 		P.push_back(u);
  96. 		L.push_back(u <= 0 ? 0 : L[u]+1);
  97. 		int nn = adj.size();
  98. 		adj.push_back(nex);
  99. 		return nn;
  100. 	}
  101. 	void dfsL(int u, int LVL = 0){
  102. 		L[u] = LVL;
  103. 		SZ[u] = 1;
  104. 		for(int v : adj[u]){
  105. 			dfsL(v, LVL+1);
  106. 			SZ[u] += SZ[v];
  107. 		}
  108. 	}
  109. 	void buildFragment(int u, Fragment &F){
  110. 		if(G[u] != -1)return;
  111. 		G[u] = frags.size() - 1;
  112. 		F.add(u);
  113. 		for(int v : adj[u]){
  114. 			buildFragment(v, F);
  115. 		}
  116. 	}
  117. 	void fragment(){
  118. 		dfsL(0);
  119. 		VVI nodesByLevel(N);
  120. 		for(int i = 0; i < N; ++i)
  121. 			nodesByLevel[ N-1-L[i] ].push_back(i);
  122. 		for(VI p : nodesByLevel){
  123. 			for(int u : p){
  124. 				vector<int> toF;
  125. 				VI temp, child = adj[u], spChild;
  126. 				int sz = 0;
  127. 				SZ[u] = 1;
  128. 				for(int v : child){
  129. 					SZ[u] += SZ[v];
  130. 				}
  131. 				for(int v : child){
  132. 					sz += SZ[v];
  133. 					temp.push_back(v);
  134. 					if(sz > SQ){
  135. 						int nn = createNode(u, temp);
  136. 						temp.clear();
  137. 						spChild.push_back(nn);
  138. 						frags.push_back(Fragment(nn, N, V, L));
  139. 						buildFragment(nn, frags.back());
  140. 						SZ[u] -= sz;
  141. 						sz = 0;
  142. 					}
  143. 				}
  144. 				adj[u] = temp;
  145. 				for(int v : spChild)
  146. 					adj[u].push_back(v);
  147. 			}
  148. 		}
  149. 		int nn = createNode(-1, VI(1,0));
  150. 		frags.push_back(Fragment(nn, N, V, L));
  151. 		buildFragment(nn, frags.back());
  152. 		adj2 = VVI(frags.size());
  153. 		for(int i = 0; i < frags.size(); ++i){
  154. 			Fragment &f = frags[i];
  155. 			if(P[f.u] == -1)continue;
  156. 			f.p = G[ P[f.u] ];
  157. 			adj2[ f.p ].push_back(i);
  158. 		}
  159. 	}
  160. 	int leader(int u){
  161. 		return frags[G[u]].u;
  162. 	}
  163. 	int lca(int u,int v){
  164. 		while(leader(u) != leader(v)){
  165. 			if(L[ leader(u) ] > L[ leader(v)]){
  166. 				u = P[ leader(u) ];
  167. 			}else{
  168. 				v = P[ leader(v) ];
  169. 			}
  170. 		}
  171. 		while(u != v){
  172.  
  173. 			if(L[v] > L[u]){
  174. 				v = P[v];
  175. 			}else{
  176. 				u = P[u];
  177. 			}
  178. 		}
  179. 		return u;
  180. 	}
  181. };
  182.  
  183. int main(){
  184.  
  185. 	int N,M;
  186. 	scanf("%d%d", &N, &M);
  187. 	int fu = -1, fv = -1;
  188. 	FragmentedTree FT(N);
  189. 	for(int i = 0; i < N-1; ++i){
  190. 		int u,v;
  191. 		scanf("%d%d", &u, &v);
  192. //		u = i+1;
  193. //		v = i+2;
  194. 		u--;v--;
  195. 		if(fu == -1){
  196. 			fu = u;
  197. 			fv = v;
  198. 		}
  199. 		FT.addEdge(u,v);
  200. 	}
  201. 	FT.fragment();
  202. //	for(FragmentedTree::Fragment f : FT.frags){
  203. //		for(int u : f.nodes){
  204. //			cout << u << " ";
  205. //		}
  206. //		cout << endl;
  207. //	}
  208. //	for(FragmentedTree::Fragment f : FT.frags){
  209. //		cout << f.p << endl;
  210. //	}
  211. //	return 0;
  212. //	if(fu == 0 && fv == 1 && N == 20000){
  213. //		cout << FT.frags.size() << endl;
  214. //	}
  215. 	for(int i = 0; i < M; ++i){
  216.  
  217.  
  218. 		int c;
  219. 		scanf("%d", &c);
  220. //		c = rand() % 2+1;
  221. 		if(c == 1){
  222. 			int L,Y;
  223. 			scanf("%d%d", &L, &Y);
  224. //			L = rand() % 2;
  225. //			Y = rand() % 1000000000 + 1;
  226. 			FT.update(L, Y);
  227. 		}else{
  228. 			int X;
  229. 			scanf("%d", &X);
  230. //			X = rand() % N + 1;
  231. 			X--;
  232. //			if(fu == 0 && fv == 10913){
  233. ////				cout << i << endl;
  234. //			}else{
  235. 				cout << FT.getSum(X) << endl;
  236. //			}
  237. 		}
  238. 	}
  239.  
  240. }
  241.  
  242.  
  243. /*
  244.  
  245. 5 4
  246. 1 2
  247. 1 3
  248. 3 4
  249. 3 5
  250. 1 1 2
  251. 1 2 3
  252. 2 3
  253. 2 1
  254.  
  255.  0 
  256. 1  2
  257.   3 4
  258.  */
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1
stdout
copy 
8
10
https://ideone.com/kM4yko
language:
C++14 (gcc 8.3)
created:
3 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!