Luogu

LOJ

分析

考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。

于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。

又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。

这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把点权放到父边上，再加上虚树的根的点权即可。

需要注意的是关键点也是虚树上的圆点，所以我们还要把关键点减掉。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,m,tot,p[N];
vector<int> E[N],T[N];

namespace tarjan {
    int dfn[N],low[N],tim=0,sta[N],top=0;
    void tarjan(int u) {
        dfn[u]=low[u]=++tim,sta[++top]=u;
        for (int v:E[u]) {
            if (!dfn[v]) {
                tarjan(v),low[u]=min(low[u],low[v]);
                if (low[v]>=dfn[u]) {
                    ++tot; T[tot].emplace_back(u),T[u].emplace_back(tot);
                    while (1) {
                        int t=sta[top--];
                        T[tot].emplace_back(t),T[t].emplace_back(tot);
                        if (t==v) break;
                    }
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
    }
}

int dep[N],fa[N],sz[N],hson[N],top[N],dis[N];
int dfn[N],tim=0;
void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1,hson[u]=0;
    for (int v:T[u]) {
        if (v==f) continue;
        dis[v]=dis[u]+(v<=n); dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim;
    if (hson[u]) dfs2(hson[u],anc);
    for (int v:T[u])
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}
int LCA(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int getdis(int u,int v) {
    return dis[u]+dis[v]-(dis[LCA(u,v)]<<1);
}

int main() {
    for (int _=read();_;--_) {
        n=read(),m=read();
        for (int i=1;i<=n;++i) E[i].clear();
        for (int i=1;i<=tot;++i) T[i].clear();
        for (int i=1;i<=n;++i) tarjan::dfn[i]=0;
        tarjan::tim=tarjan::top=dep[0]=dis[1]=tim=0;
        for (int i=1;i<=m;++i) {
            int u=read(),v=read();
            E[u].emplace_back(v),E[v].emplace_back(u);
        }
        tot=n; tarjan::tarjan(1); dfs1(1,0),dfs2(1,1);
        for (int Q=read();Q;--Q) {
            int k=read();
            for (int i=1;i<=k;++i) p[i]=read();
            sort(p+1,p+k+1,[](int x,int y) { return dfn[x]<dfn[y]; });
            int ans=0;
            for (int i=1;i<=k;++i) ans+=getdis(p[i],p[i%k+1]);
            ans=ans/2+(LCA(p[1],p[k])<=n);
            printf("%d\n",ans-k);
        }
    }
    return 0;
}