1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
| #include <bits/stdc++.h> #define N 300005 using namespace std;
template <typename T> inline void read(T &num) { T x = 0, ff = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') ff = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * ff; } template <typename T> void write(T num) { if (num < 0) putchar('-'), num = -num; if (num > 9) write(num/10); putchar(num%10+'0'); }
int ttt, n, P, m, Q, K; int head[N], pre[N<<1], to[N<<1], sz; int dfn[N], dfsx[N], low[N], tme, stk[N], top, pp[N]; vector<int> e[N]; int d[N], p[N][21], sum[N];
void init_TU() { memset(head, 0, sizeof(head)); sz = 0; } void init_OTHERS() { for (int i = 1; i <= n; i++) e[i].clear(); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); tme = 0; memset(stk, 0, sizeof(stk)); top = 0; memset(dfsx, 0, sizeof(dfsx)); memset(d, 0, sizeof(d)); memset(p, 0, sizeof(p)); memset(sum, 0, sizeof(sum)); } void initALL() { init_TU(); init_OTHERS(); } void addedge(int u, int v) { pre[++sz] = head[u]; head[u] = sz; to[sz] = v; pre[++sz] = head[v]; head[v] = sz; to[sz] = u; }
void tarjan(int x) { dfn[x] = low[x] = ++tme; stk[++top] = x; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if (low[y] == dfn[x]) { int z = 0; ++n; do { z = stk[top--]; e[z].push_back(n); e[n].push_back(z); } while (z != y); e[x].push_back(n); e[n].push_back(x); } } else low[x] = min(low[x], dfn[y]); } }
void dfs(int x, int fa) { dfsx[x] = ++tme; sum[x] = (x <= P) + sum[fa]; for (int l = 1; (1 << l) <= n; l++) p[x][l] = p[p[x][l-1]][l-1]; for (auto y : e[x]) { if (y == fa) continue; d[y] = d[x] + 1; p[y][0] = x; dfs(y, x); } } inline int LCA(int x, int y) { if (d[x] < d[y]) swap(x, y); for (int i = 20; ~i; i--) if (d[x]-(1<<i)>=d[y]) x = p[x][i]; if (x == y) return x; for (int i = 20; ~i; i--) if (p[x][i] != p[y][i]) x = p[x][i], y = p[y][i]; return p[x][0]; } bool cmp(int x, int y) { return dfsx[x] < dfsx[y]; } int solve() { top = 0; int ans = 0; for (int i = 1; i <= K; i++) { if (!top) { stk[++top] = pp[i]; continue; } int lca = LCA(stk[top], pp[i]); while (top > 1 && dfsx[stk[top-1]] >= dfsx[lca]) { ans += sum[stk[top]]-sum[stk[top-1]]; --top; } if (stk[top] != lca) { ans += sum[stk[top]]-sum[lca]; stk[top] = lca; } stk[++top] = pp[i]; } while (top > 1) { ans += sum[stk[top]]-sum[stk[top-1]]; --top; } ans += (stk[top] <= P); return ans - K; } int main() { read(ttt); while (ttt--) { initALL(); read(n); read(m); P = n; for (int i = 1, u, v; i <= m; i++) { read(u); read(v); addedge(u, v); } tarjan(1); tme = 0; dfs(1, 0); read(Q); for (int kk = 1; kk <= Q; kk++) { read(K); for (int i = 1; i <= K; i++) read(pp[i]); sort(pp + 1, pp + K + 1, cmp); write(solve()); puts(""); } } return 0; }
|