fork(52) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 40005;
  5. const int MAXM = 100005;
  6. const int LN = 19;
  7.  
  8. int N, M, K, cur, A[MAXN], LVL[MAXN], DP[LN][MAXN];
  9. int BL[MAXN << 1], ID[MAXN << 1], VAL[MAXN], ANS[MAXM];
  10. int d[MAXN], l[MAXN], r[MAXN];
  11. bool VIS[MAXN];
  12. vector < int > adjList[MAXN];
  13.  
  14. struct query{
  15. 	int id, l, r, lc;
  16. 	bool operator < (const query& rhs){
  17. 		return (BL[l] == BL[rhs.l]) ? (r < rhs.r) : (BL[l] < BL[rhs.l]);
  18. 	}
  19. }Q[MAXM];
  20.  
  21. // Set up Stuff
  22. void dfs(int u, int par){
  23. 	l[u] = ++cur; 
  24. 	ID[cur] = u;
  25. 	for (int i = 1; i < LN; i++) DP[i][u] = DP[i - 1][DP[i - 1][u]];
  26. 	for (int i = 0; i < adjList[u].size(); i++){
  27. 		int v = adjList[u][i];
  28. 		if (v == par) continue;
  29. 		LVL[v] = LVL[u] + 1;
  30. 		DP[0][v] = u;
  31. 		dfs(v, u);
  32. 	}
  33. 	r[u] = ++cur; ID[cur] = u;
  34. }
  35.  
  36. // Function returns lca of (u) and (v)
  37. inline int lca(int u, int v){
  38. 	if (LVL[u] > LVL[v]) swap(u, v);
  39. 	for (int i = LN - 1; i >= 0; i--)
  40. 		if (LVL[v] - (1 << i) >= LVL[u]) v = DP[i][v];
  41. 	if (u == v) return u;
  42. 	for (int i = LN - 1; i >= 0; i--){
  43. 		if (DP[i][u] != DP[i][v]){
  44. 			u = DP[i][u];
  45. 			v = DP[i][v];
  46. 		}
  47. 	}
  48. 	return DP[0][u];
  49. }
  50.  
  51. inline void check(int x, int& res){
  52. 	// If (x) occurs twice, then don't consider it's value 
  53. 	if ( (VIS[x]) and (--VAL[A[x]] == 0) ) res--; 
  54. 	else if ( (!VIS[x]) and (VAL[A[x]]++ == 0) ) res++;
  55. 	VIS[x] ^= 1;
  56. }
  57.  
  58. void compute(){
  59.  
  60. 	// Perform standard Mo's Algorithm
  61. 	int curL = Q[0].l, curR = Q[0].l - 1, res = 0;
  62.  
  63. 	for (int i = 0; i < M; i++){
  64.  
  65. 		while (curL < Q[i].l) check(ID[curL++], res);
  66. 		while (curL > Q[i].l) check(ID[--curL], res);
  67. 		while (curR < Q[i].r) check(ID[++curR], res);
  68. 		while (curR > Q[i].r) check(ID[curR--], res);
  69.  
  70. 		int u = ID[curL], v = ID[curR];
  71.  
  72. 		// Case 2
  73. 		if (Q[i].lc != u and Q[i].lc != v) check(Q[i].lc, res);
  74.  
  75. 		ANS[Q[i].id] = res;
  76.  
  77. 		if (Q[i].lc != u and Q[i].lc != v) check(Q[i].lc, res);
  78. 	}
  79.  
  80. 	for (int i = 0; i < M; i++) printf("%d\n", ANS[i]);
  81. }
  82.  
  83. int main(){
  84.  
  85. 	int u, v, x;
  86.  
  87. 	while (scanf("%d %d", &N, &M) != EOF){
  88.  
  89. 		// Cleanup
  90. 		cur = 0;
  91. 		memset(VIS, 0, sizeof(VIS));
  92. 		memset(VAL, 0, sizeof(VAL));
  93. 		for (int i = 1; i <= N; i++) adjList[i].clear();
  94.  
  95. 		// Inputting Values
  96. 		for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  97. 		memcpy(d + 1, A + 1, sizeof(int) * N);
  98.  
  99. 		// Compressing Coordinates
  100. 		sort(d + 1, d + N + 1);
  101. 		K = unique(d + 1, d + N + 1) - d - 1;
  102. 		for (int i = 1; i <= N; i++) A[i] = lower_bound(d + 1, d + K + 1, A[i]) - d;
  103.  
  104. 		// Inputting Tree
  105. 		for (int i = 1; i < N; i++){
  106. 			scanf("%d %d", &u, &v);
  107. 			adjList[u].push_back(v);
  108. 			adjList[v].push_back(u);
  109. 		}
  110.  
  111. 		// Preprocess
  112. 		DP[0][1] = 1;
  113. 		dfs(1, -1);
  114. 		int size = sqrt(cur);
  115.  
  116. 		for (int i = 1; i <= cur; i++) BL[i] = (i - 1) / size + 1;
  117.  
  118. 		for (int i = 0; i < M; i++){
  119. 			scanf("%d %d", &u, &v);
  120. 			Q[i].lc = lca(u, v);
  121. 			if (l[u] > l[v]) swap(u, v);
  122. 			if (Q[i].lc == u) Q[i].l = l[u], Q[i].r = l[v];
  123. 			else Q[i].l = r[u], Q[i].r = l[v];
  124. 			Q[i].id = i;
  125. 		}
  126.  
  127. 		sort(Q, Q + M);
  128. 		compute();
  129. 	}
  130. }
  131.  
Success #stdin #stdout 0s 10472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6NVoPD
language:
C++14 (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!