fork(1) download
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <queue>
  5. #include <cmath>
  6. #include <utility>
  7. #include <unordered_map>
  8. #include <set>
  9. #include <map>
  10.  
  11. #include <ext/pb_ds/assoc_container.hpp>
  12. #include <ext/pb_ds/tree_policy.hpp>
  13.  
  14. #define ll long long
  15. #define p1 first
  16. #define p2 second
  17. #define pii pair<int,int>
  18. #define MAXINT (1 << 30)
  19. #define MAXLL (1LL << 60)
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. struct cmp {
  24. bool operator()(pii const a, pii const b) const {
  25. if (a.p1 == b.p1) return a.p2 < b.p2;
  26. else return a.p1 < b.p1;
  27. }
  28. };
  29.  
  30.  
  31. typedef tree<pii, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  32.  
  33. /*
  34. Data Structures: Range Trees, Trees.
  35. Algorithms: DFS.
  36.  
  37. Time Complexity: O(nlog^2(n))
  38. */
  39.  
  40. vector<vector<int>> edges;
  41. vector<int> val;
  42. vector<int> in;
  43. vector<int> out;
  44. vector<ordered_set> rt;
  45. int marker = 0;
  46. int n;
  47. int sz;
  48. int marker1 = 0;
  49.  
  50. void dfs(int i, int p) {
  51. in[i] = ++marker;
  52. for (int u : edges[i]) {
  53. if (p == u) continue; // skip parent
  54. dfs(u, i);
  55. }
  56. out[i] = marker;
  57. }
  58.  
  59. void buildTree(int p, int item, int l = 1, int r = n, int i = 1) {
  60. rt[i].insert({item, ++marker1});
  61. if (l != r) {
  62. int m = (l + r) >> 1;
  63. if (in[p] <= m) buildTree(p, item, l, m, i << 1);
  64. else buildTree(p, item, m + 1, r, i << 1 | 1);
  65. }
  66. }
  67.  
  68. int qTree(int p, int item, int l = 1, int r = n, int i = 1) {
  69. if (r < in[p]) return 0;
  70. else if (in[p] <= l && r <= out[p]) {
  71. return rt[i].order_of_key({item,0});
  72. }
  73. int sum = 0;
  74. if (l != r) {
  75. int m = (l + r) >> 1;
  76. sum += qTree(p,item, l, m, i << 1);
  77. sum += qTree(p,item, m + 1, r, i << 1 | 1);
  78. }
  79.  
  80. return sum;
  81. }
  82. int main() {
  83. int q, u, v;
  84. scanf("%d %d", &n, &q);
  85. val.resize(n);
  86. in.resize(n);
  87. out.resize(n);
  88. edges.resize(n);
  89.  
  90. int sz = 2 << (int)ceil(log(n) / log(2));
  91. rt.resize(sz);
  92.  
  93. for (int i = 0; i < n; i++) {
  94. scanf("%d", &v);
  95. val[i] = v;
  96. }
  97.  
  98. for (int i = 0; i < n - 1; i++) {
  99. scanf("%d %d", &u, &v);
  100. edges[u].push_back(v);
  101. edges[v].push_back(u);
  102. }
  103. dfs(0, -1);
  104. for (int i = 0; i < n; i++) {
  105. buildTree(i, val[i]);
  106. }
  107. int nd; int s;
  108. for (int i = 0; i < q; i++) {
  109. scanf("%d %d", &nd, &s);
  110. if (s == 0) printf("0\n");
  111. else printf("%d\n", qTree(nd, s));
  112. buildTree(nd, s);
  113. }
  114. }
Success #stdin #stdout 0s 4332KB
stdin
7 8
10 9 13 17 11 20 18
0 4
0 1
1 2
1 3
2 5
2 6
0 21
0 8
2 15
3 22
1 14
2 19
0 12
1 16
stdout
7
0
1
1
2
3
4
4