fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int, int> pii;
  6.  
  7. #define F first
  8. #define S second
  9. #define tm lkjsdaf
  10.  
  11. const int MAXN = 1e5 + 10;
  12. const int LOG = 17;
  13.  
  14. int n, q;
  15. vector<pii> adj[MAXN];
  16. int cntEdge[MAXN][2], cntVertices;
  17.  
  18. int par[LOG][MAXN], parColor[MAXN], sub[MAXN], depth[MAXN];
  19. bool cmpEdges(pii e1, pii e2){return sub[e1.F] > sub[e2.F];}
  20.  
  21. //------------HLD Prep
  22.  
  23. int heavyPar[MAXN], heavyChild[MAXN];
  24. int dfsInitHld(int v, int p = -1, int pc = -1){
  25. 	par[0][v] = p, parColor[v] = pc;
  26. 	depth[v] = (p==-1? 0: depth[p]+1);
  27. 	if (~p)
  28. 		adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(p, pc)));
  29.  
  30. 	sub[v] = 1;
  31. 	for (auto e:adj[v])
  32. 		sub[v] += dfsInitHld(e.F, v, e.S);
  33.  
  34. 	sort(adj[v].begin(), adj[v].end(), cmpEdges);
  35. 	return sub[v];
  36. }
  37.  
  38. int hldRoot[MAXN], st[MAXN], ft[MAXN], tm, ord[MAXN];
  39. void dfsBuildHld(int v, int rt = -1){
  40. 	heavyPar[v] = heavyChild[v] = -1;
  41.  
  42. 	ord[tm] = v;
  43. 	st[v] = tm++;
  44. 	if (rt == -1)
  45. 		rt = v;
  46. 	else
  47. 		heavyPar[v] = par[0][v], cntEdge[v][parColor[v]]--;
  48. 	hldRoot[v] = rt;
  49.  
  50. 	for (auto e:adj[v]) {
  51. 		if (rt != -1) {
  52. 			heavyChild[v] = e.F;
  53. 			cntEdge[v][parColor[e.F]]--;
  54. 		}
  55. 		dfsBuildHld(e.F, rt);
  56. 		rt = -1;
  57. 	}
  58.  
  59. 	ft[v] = tm;
  60. }
  61.  
  62.  
  63.  
  64. //------------LCA
  65.  
  66. void preLca(){
  67. 	for (int w = 1; w < LOG; w++)
  68. 		for (int v = 0; v < n; v++)
  69. 			if (par[w-1][v] == -1)
  70. 				par[w][v] = -1;
  71. 			else
  72. 				par[w][v] = par[w-1][par[w-1][v]];
  73. }
  74.  
  75. int lca(int u, int v){
  76. 	if (depth[u] < depth[v]) 
  77. 		swap(u, v);
  78. 	for (int w = LOG-1; ~w; w--)
  79. 		if (depth[u] - (1<<w) >= depth[v])
  80. 			u = par[w][u];
  81. 	if (u == v) return u;
  82.  
  83. 	for (int w = LOG-1; ~w; w--)
  84. 		if (par[w][u] ^ par[w][v])
  85. 			u = par[w][u], v = par[w][v];
  86. 	return par[0][u];
  87. }
  88.  
  89.  
  90.  
  91. //-----------Edge Segment
  92.  
  93. int edgeSeg[MAXN<<2];
  94. int getEdgeColor(int v, int b, int e, int pos, int cur = 0){
  95. 	cur ^= edgeSeg[v];
  96. 	if (e - b == 1)
  97. 		return parColor[ord[pos]]^cur;
  98.  
  99. 	int mid = b + e >> 1;
  100. 	return pos < mid? getEdgeColor(v<<1, b, mid, pos, cur): getEdgeColor(v<<1^1, mid, e, pos, cur);
  101. }
  102.  
  103. void changeColor(int v, int b, int e, int l, int r){
  104. 	if (l <= b && e <= r){
  105. 		edgeSeg[v]^=1;
  106. 		return;
  107. 	}
  108. 	if (r <= b || e <= l) return;
  109.  
  110. 	int mid = b + e >> 1;
  111. 	changeColor(v<<1, b, mid, l, r);
  112. 	changeColor(v<<1^1, mid, e, l, r);
  113. }
  114.  
  115.  
  116. //-------------Main Segment
  117. int tempCol[2][2];
  118. void fillTempCol(int v, int t){
  119. 	if (~heavyChild[v])
  120. 		tempCol[t][getEdgeColor(1, 0, n, st[heavyChild[v]])]++;
  121. 	if (~heavyPar[v])
  122. 		tempCol[t][getEdgeColor(1, 0, n, st[v])]++;
  123. }
  124.  
  125. int cnt[3][MAXN<<2], lz[MAXN<<2];
  126. int getGoodVertices(int v, int b, int e, int l, int r){
  127. 	if (l <= b && e <= r) return cnt[1][v] + cnt[2][v];
  128. 	if (r <= b || e <= l) return 0;
  129.  
  130. 	int mid = b + e >> 1;
  131. 	return getGoodVertices(v<<1, b, mid, l, r) + getGoodVertices(v<<1^1, mid, e, l, r);
  132. }
  133.  
  134. void pushDown(int v){
  135. 	if (!lz[v]) return;
  136.  
  137. 	for (int i = 0; i < 2; i++){
  138. 		lz[v<<1^i] ^= 1;
  139. 		swap(cnt[0][v<<1^i], cnt[1][v<<1^i]);
  140. 	}
  141.  
  142. 	lz[v] = 0;
  143. }
  144.  
  145. void merge(int v){
  146. 	for (int w = 0; w < 3; w++)
  147. 		cnt[w][v] = cnt[w][v<<1] + cnt[w][v<<1^1];
  148. }
  149.  
  150. void flip(int v, int b, int e, int l, int r){
  151. 	if (l <= b && e <= r){
  152. 		lz[v]^=1;
  153. 		swap(cnt[0][v], cnt[1][v]);
  154. 		return;
  155. 	}
  156. 	if (r <= b || e <= l) return;
  157.  
  158. 	int mid = b + e >> 1;
  159. 	pushDown(v);
  160. 	flip(v<<1, b, mid, l, r);
  161. 	flip(v<<1^1, mid, e, l, r);
  162. 	merge(v);
  163. }
  164.  
  165. void setPos(int v, int u, int z = -1){
  166. 	for (int w = 0; w < 3; w++)
  167. 		cnt[w][v] = 0;
  168. 	if (cntEdge[u][0] > 0 && cntEdge[u][1] > 0) return;
  169.  
  170. 	if (z == -1){
  171. 		memset(tempCol, 0, sizeof(tempCol));
  172. 		fillTempCol(u, 0);
  173. 		z = 0;
  174. 	}
  175.  
  176. 	if (tempCol[0][0] > 0 && tempCol[0][1] > 0) return;
  177. 	if (cntEdge[u][0] + cntEdge[u][1] == 0 || tempCol[0][0] + tempCol[0][1] == 0)
  178. 		cnt[2][v] = 1;
  179. 	else if ((cntEdge[u][0] > 0 && tempCol[0][0] > 0) || (cntEdge[u][1] > 0 && tempCol[0][1] > 0))
  180. 		cnt[1][v] = 1;
  181. 	else
  182. 		cnt[0][v] = 1;
  183. }
  184.  
  185. void updatePos(int v, int b, int e, int pos, int z = -1){
  186. 	if (e - b == 1){
  187. 		setPos(v, ord[b], z);
  188. 		return;
  189. 	}
  190.  
  191. 	int mid = b + e >> 1;
  192. 	pushDown(v);
  193. 	if (pos < mid)
  194. 		updatePos(v<<1, b, mid, pos);
  195. 	else
  196. 		updatePos(v<<1^1, mid, e, pos);
  197. 	merge(v);
  198. }
  199.  
  200. void plantMainSeg(int v, int b, int e){
  201. 	lz[v] = 0;
  202. 	if (e - b == 1){
  203. 		setPos(v, ord[b]);
  204. 		return;
  205. 	}
  206.  
  207. 	int mid = b + e >> 1;
  208. 	plantMainSeg(v<<1, b, mid);
  209. 	plantMainSeg(v<<1^1, mid, e);
  210. 	merge(v);
  211. }
  212.  
  213. //-------------Handling Query
  214.  
  215. void dealWithHeavyPath(int v, int p){
  216. 	if (v == p) return;
  217.  
  218. 	memset(tempCol, 0, sizeof(tempCol));
  219. 	fillTempCol(v, 0);
  220. 	fillTempCol(p, 1);
  221. 	if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices--;
  222. 	if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices--;
  223.  
  224. 	changeColor(1, 0, n, st[p]+1, st[v]+1);
  225.  
  226. 	memset(tempCol, 0, sizeof(tempCol));
  227. 	fillTempCol(v, 0);
  228. 	fillTempCol(p, 1);
  229. 	if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices++;
  230. 	if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices++;
  231. 	if (hldRoot[v] != v && adj[v].size())
  232. 		updatePos(1, 0, n, st[v], 0);
  233. 	if (hldRoot[p] != p)
  234. 		updatePos(1, 0, n, st[p], 1);
  235.  
  236. 	if (depth[v]-1 > depth[p]){//There's a real path to deal with
  237. 		cntVertices -= getGoodVertices(1, 0, n, st[p]+1, st[v]);
  238. 		flip(1, 0, n, st[p]+1, st[v]);
  239. 		cntVertices += getGoodVertices(1, 0, n, st[p]+1, st[v]);
  240. 	}
  241. }
  242.  
  243. void dealWithLightEdge(int v){
  244. 	int p = par[0][v];
  245. 	memset(tempCol, 0, sizeof(tempCol));
  246. 	fillTempCol(v, 0);
  247. 	fillTempCol(p, 1);
  248.  
  249. 	if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices--;
  250. 	if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices--;
  251.  
  252. 	cntEdge[v][parColor[v]]--;
  253. 	cntEdge[p][parColor[v]]--;
  254.  
  255. 	parColor[v] ^= 1;
  256.  
  257. 	cntEdge[v][parColor[v]]++;
  258. 	cntEdge[p][parColor[v]]++;
  259. 	if (cntEdge[v][0] + tempCol[0][0] == 0 || cntEdge[v][1] + tempCol[0][1] == 0) cntVertices++;
  260. 	if (cntEdge[p][0] + tempCol[1][0] == 0 || cntEdge[p][1] + tempCol[1][1] == 0) cntVertices++;
  261. 	//updatePos(1, 0, n, st[v], 0);
  262. 	if (hldRoot[p] != p)
  263. 		updatePos(1, 0, n, st[p], 1);
  264. }
  265.  
  266. void dealWith(int v, int p){
  267. 	if (v == p) return;
  268.  
  269. 	while (depth[v] > depth[p]){
  270. 		int rt = hldRoot[v];
  271. 		if (depth[rt] < depth[p]) rt = p;
  272. 		dealWithHeavyPath(v, rt);
  273.  
  274. 		v = rt;
  275. 		if (v == p) break;
  276. 		dealWithLightEdge(v);
  277. 		v = par[0][v];
  278. 	}
  279. }
  280.  
  281. void debug(int v, int b, int e){
  282. 	cout << v << "  " << b << " " << e << "      ";
  283. 	for (int w = 0; w < 3; w++)
  284. 		cout << cnt[w][v] << " ";
  285. 	cout << lz[v] << " ";
  286. 	cout << endl;
  287.  
  288. 	if (e - b == 1) return;
  289.  
  290. 	int mid = b + e >> 1;
  291. 	pushDown(v);
  292. 	debug(v<<1, b, mid);
  293. 	debug(v<<1^1, mid, e);
  294. }
  295.  
  296. int main() {
  297. 	ios::sync_with_stdio(false);
  298. 	cin.tie(0);
  299. 	int te;	cin >> te;
  300. 	while (te--){
  301. 		cin >> n;
  302. 		for (int i = 0; i < n; i++) adj[i].clear();
  303. 		for (int i = 0; i < n-1; i++){
  304. 			int a, b, c; cin >> a >> b >> c, a--, b--;
  305. 			adj[a].push_back({b, c});
  306. 			adj[b].push_back({a, c});
  307. 		}
  308. 		cntVertices = 0;
  309. 		for (int v = 0; v < n; v++){
  310. 			cntEdge[v][0] = cntEdge[v][1] = 0;
  311. 			for (auto e:adj[v])
  312. 				cntEdge[v][e.S]++;
  313. 			cntVertices += int(cntEdge[v][0]==0 || cntEdge[v][1]==0);
  314. 		}
  315. 		dfsInitHld(0);
  316. 		preLca();
  317. 		tm = 0;
  318. 		dfsBuildHld(0);
  319. 		fill(edgeSeg, edgeSeg + 4*(n+2), 0);
  320.  
  321. 		plantMainSeg(1, 0, n);
  322.  
  323. 		int q; cin >> q;
  324. 		while (q--){
  325. 			int u, v; cin >> u >> v, u--, v--;
  326. 			int p = lca(u, v);
  327. 	//		debug(1, 0, n);
  328. 			dealWith(u, p);
  329. 			dealWith(v, p);
  330. 			cout << 1 + (n - cntVertices) << "\n";
  331. 		}
  332. 	}
  333. 	return 0;
  334. }
Runtime error #stdin #stdout 0s 36344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aF0MNe
language:
C++14 (gcc 8.3)
created:
4 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!