\(\mathcal{Description}\)

  Link.

  给定一个 \(n\) 个点 \(m\) 条边的无向连通图，\(q\) 次询问，每次给出一个点集 \(s\)，求至少在原图中删去多少个点，使得 \(s\) 中存在两点不连通。多组数据。

  每组数据 \(n,q\le10^5\)，\(m,\sum|s|\le2\times10^5\)。

\(\mathcal{Solution}\)

  看到 \(\sum|s|\) 的限制，不难联想到虚树或者其它与 DFN 相关的算法。

  所以，先建出圆方树，并处理好 DFN，LCA 的一系列信息。考虑到答案就是 \(s\) 中的点在树上构成的连通块中不在 \(s\) 集合里的圆点个数，可以求一个树上前缀和：\(sum_u\) 表示从 \(u\) 到根路径上的圆点个数。处理询问时，先将 \(s\) 按 DFN 从小到大排序，两两 LCA 计算贡献（\(s_1\) 和 \(s_{|s|}\) 也要算一次），最后除以 \(2\)，得到 \(cnt\)。不过整个连通块的根（\(\operatorname{LCA}(s_1,s_{|s|})\)）这个点的贡献被遗漏了，所以要再加上这个点单独的贡献。最终答案就是 \(cnt-|s|\)。

  复杂度 \(\mathcal O(T(n\log n+\sum|s|\log\sum|s|))\)。

  就是练练码力的一道题嘛 qwq。

#include <queue>
#include <cstdio>
#include <algorithm>

#define adj( g, u, v ) \
    for ( int eid = g.head[u], v; v = g.to[eid], eid; eid = g.nxt[eid] )

const int MAXN = 2e5, MAXM = 4e5;
int n, m, q, snode;
int dfc, top, dfn[MAXN + 5], low[MAXN + 5], stk[MAXN + 5];
int lg[MAXN * 2 + 5], dep[MAXN + 5], st[MAXN * 2 + 5][20], sum[MAXN + 5];

struct Graph {
    int ecnt, head[MAXN + 5], to[MAXM + 5], nxt[MAXM + 5];
    inline void link ( const int s, const int t ) {
        to[++ ecnt] = t, nxt[ecnt] = head[s];
        head[s] = ecnt;
    }
    inline void add ( const int u, const int v ) {
        link ( u, v ), link ( v, u );
    }
    inline void clear () {
        ecnt = 0;
        for ( int i = 1; i <= n << 1; ++ i ) head[i] = 0;
    }
} src, tre;

inline int rint () {
    int x = 0; char s = getchar ();
    for ( ; s < '0' || '9' < s; s = getchar () );
    for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
    return x;
}

inline bool chkmin ( int& a, const int b ) { return b < a ? a = b, true : false; }

inline void clear () {
    src.clear (), tre.clear ();
    dfc = top = snode = 0;
    for ( int i = 1; i <= n << 1; ++ i ) dfn[i] = low[i] = 0;
}

inline void Tarjan ( const int u, const int f ) {
    dfn[u] = low[u] = ++ dfc, stk[++ top] = u;
    adj ( src, u, v ) if ( v ^ f ) {
        if ( ! dfn[v] ) {
            Tarjan ( v, u ), chkmin ( low[u], low[v] );
            if ( low[v] >= dfn[u] ) {
                tre.add ( u, ++ snode );
                do tre.add ( snode, stk[top] ); while ( stk[top --] ^ v );
            }
        } else chkmin ( low[u], dfn[v] );
    }
}

inline void initDFN ( const int u, const int f ) {
    dep[st[dfn[u] = ++ dfc][0] = u] = dep[f] + 1, sum[u] = sum[f] + ( u <= n );
    adj ( tre, u, v ) if ( v ^ f ) initDFN ( v, u ), st[++ dfc][0] = u;
}

inline void initST () {
    for ( int i = 2; i <= n << 2; ++ i ) lg[i] = lg[i >> 1] + 1;
    for ( int j = 1; 1 << j <= dfc; ++ j ) {
        for ( int i = 1; i + ( 1 << j ) - 1 <= dfc; ++ i ) {
            if ( dep[st[i][j - 1]] < dep[st[i + ( 1 << j >> 1 )][j - 1]] ) st[i][j] = st[i][j - 1];
            else st[i][j] = st[i + ( 1 << j >> 1 )][j - 1];
        }
    }
}

inline int calcLCA ( int u, int v ) {
    if ( dfn[u] > dfn[v] ) u ^= v ^= u ^= v;
    int k = lg[dfn[v] - dfn[u] + 1];
    return dep[st[dfn[u]][k]] < dep[st[dfn[v] - ( 1 << k ) + 1][k]] ?
            st[dfn[u]][k] : st[dfn[v] - ( 1 << k ) + 1][k];
}

inline void solve () {
    static int cnts, s[MAXN + 5];
    cnts = rint ();
    for ( int i = 1; i <= cnts; ++ i ) s[i] = rint ();
    std::sort ( s + 1, s + cnts + 1, []( const int a, const int b ) { return dfn[a] < dfn[b]; } );
    int cnt = 0;
    for ( int i = 1; i < cnts; ++ i ) {
        int u = s[i], v = s[i + 1], t = calcLCA ( u, v );
        cnt += sum[u] + sum[v] - 2 * sum[t];
    }
    int u = s[1], v = s[cnts], t = calcLCA ( u, v );
    cnt += sum[u] + sum[v] - 2 * sum[t];
    cnt /= 2, cnt += ( t <= n ) - cnts;
    printf ( "%d\n", cnt );
}

int main () {
    for ( int T = rint (); T --; clear () ) {
        n = snode = rint (), m = rint ();
        for ( int i = 1, u, v; i <= m; ++ i ) {
            u = rint (), v = rint ();
            src.add ( u, v );
        }
        Tarjan ( 1, 0 ), dfc = 0;
        initDFN ( 1, 0 ), initST ();
        for ( q = rint (); q --; ) solve ();
    }
    return 0;
}