Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <ctime>
- #include <random>
- #include <cassert>
- #include <memory.h>
- #include <chrono>
- //#define int long long
- #define intt __int128
- #define itn int
- #define pii pair<int,int>
- #define pb push_back
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define fir first
- #define sec second
- #define INF 200000000000009
- #define EPS 0.0000001
- #define double long double
- #define sp system("pause")
- #define endl '\n'
- using namespace std;
- const int N = 1000003, MOD = 1e9 + 7, ABC = 400001, logn = 19;
- int cur = 0;
- void dfs(vector<vector<int>>& gr, vector<int>& d, vector<vector<int>>& up, vector<int>& tin, int v, int pr) {
- tin[v] = cur;
- cur++;
- d[v] = d[pr] + 1;
- up[0][v] = pr;
- for (int i = 1; i < logn; i++) {
- up[i][v] = up[i - 1][up[i - 1][v]];
- }
- for (int i : gr[v])
- if (i != pr)
- dfs(gr, d, up, tin, i, v);
- }
- int lca(vector<vector<int>>& up, vector<int>& d, int a, int b) {
- if (d[a] < d[b])
- swap(a, b);
- for (int i = logn - 1; i >= 0; i--) {
- int pa = up[i][a];
- if (d[pa] >= d[b]) {
- a = pa;
- }
- }
- if (a == b)
- return a;
- for (int i = logn - 1; i >= 0; i--) {
- int pa = up[i][a];
- int pb = up[i][b];
- if (pa != pb) {
- a = pa, b = pb;
- }
- }
- return up[0][a];
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.precision(17);
- cout << fixed;
- int n;
- cin >> n;
- vector<vector<int>> gr(n);
- int root = 0;
- for (int i = 0; i < n; i++) {
- int a;
- cin >> a;
- if (a == -1)
- root = i;
- else {
- a--;
- gr[a].push_back(i);
- }
- }
- vector<int>d(n);
- vector<int> tin(n);
- vector<vector<int>> up(logn, vector<int>(n));
- dfs(gr, d, up, tin, root, root);
- int q;
- cin >> q;
- while (q--) {
- int m;
- cin >> m;
- vector<pii> g;
- for (int i = 0; i < m; i++) {
- int a;
- cin >> a;
- a--;
- g.push_back({ tin[a], a });
- }
- g.push_back({ tin[root], root });
- sort(all(g));
- m = g.size();
- int ans = 1;
- for (int i = 1; i < m; i++) {
- int a = lca(up, d, g[i - 1].second, g[i].sec);
- ans += d[g[i].sec] - d[a];
- }
- cout << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement