fork(45) download
  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
stdin
Standard input is empty
stdout
Standard output is empty