Advertisement
ke_timofeeva7

Untitled

Oct 30th, 2023
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <set>
  7. #include <map>
  8. #include <unordered_set>
  9. #include <unordered_map>
  10. #include <stack>
  11. #include <queue>
  12. #include <deque>
  13. #include <ctime>
  14. #include <random>
  15. #include <cassert>
  16. #include <memory.h>
  17. #include <chrono>
  18. //#define int long long
  19. #define intt __int128
  20. #define itn int
  21. #define pii pair<int,int>
  22. #define pb push_back
  23. #define all(v) v.begin(), v.end()
  24. #define rall(v) v.rbegin(), v.rend()
  25. #define fir first
  26. #define sec second
  27. #define INF 200000000000009
  28. #define EPS 0.0000001
  29. #define double long double
  30. #define sp system("pause")
  31. #define endl '\n'
  32. using namespace std;
  33.  
  34. const int N = 1000003, MOD = 1e9 + 7, ABC = 400001, logn = 19;
  35.  
  36. int cur = 0;
  37. void dfs(vector<vector<int>>& gr, vector<int>& d, vector<vector<int>>& up, vector<int>& tin, int v, int pr) {
  38. tin[v] = cur;
  39. cur++;
  40. d[v] = d[pr] + 1;
  41. up[0][v] = pr;
  42. for (int i = 1; i < logn; i++) {
  43. up[i][v] = up[i - 1][up[i - 1][v]];
  44. }
  45. for (int i : gr[v])
  46. if (i != pr)
  47. dfs(gr, d, up, tin, i, v);
  48. }
  49.  
  50. int lca(vector<vector<int>>& up, vector<int>& d, int a, int b) {
  51. if (d[a] < d[b])
  52. swap(a, b);
  53. for (int i = logn - 1; i >= 0; i--) {
  54. int pa = up[i][a];
  55. if (d[pa] >= d[b]) {
  56. a = pa;
  57. }
  58. }
  59. if (a == b)
  60. return a;
  61. for (int i = logn - 1; i >= 0; i--) {
  62. int pa = up[i][a];
  63. int pb = up[i][b];
  64. if (pa != pb) {
  65. a = pa, b = pb;
  66. }
  67. }
  68. return up[0][a];
  69. }
  70.  
  71. signed main() {
  72. ios_base::sync_with_stdio(false);
  73. cin.tie(nullptr);
  74. cout.precision(17);
  75. cout << fixed;
  76.  
  77. int n;
  78. cin >> n;
  79.  
  80. vector<vector<int>> gr(n);
  81. int root = 0;
  82. for (int i = 0; i < n; i++) {
  83. int a;
  84. cin >> a;
  85. if (a == -1)
  86. root = i;
  87. else {
  88. a--;
  89. gr[a].push_back(i);
  90. }
  91. }
  92. vector<int>d(n);
  93. vector<int> tin(n);
  94. vector<vector<int>> up(logn, vector<int>(n));
  95. dfs(gr, d, up, tin, root, root);
  96. int q;
  97. cin >> q;
  98. while (q--) {
  99. int m;
  100. cin >> m;
  101. vector<pii> g;
  102. for (int i = 0; i < m; i++) {
  103. int a;
  104. cin >> a;
  105. a--;
  106. g.push_back({ tin[a], a });
  107. }
  108. g.push_back({ tin[root], root });
  109. sort(all(g));
  110. m = g.size();
  111. int ans = 1;
  112. for (int i = 1; i < m; i++) {
  113. int a = lca(up, d, g[i - 1].second, g[i].sec);
  114. ans += d[g[i].sec] - d[a];
  115. }
  116. cout << ans << endl;
  117. }
  118. return 0;
  119. }
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement