5329: [Sdoi2018]战略游戏

5329: [Sdoi2018]战略游戏

链接

分析：

　　建出圆方树，那么求的就是点集中所有点的构成的联通块的圆点的个数，然后转化为路径和+[根节点为圆点]。

　　按照dfs序排序，然后答案等于相邻两个点之间的路径和，除以2。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fore(i, u, v) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
using namespace std;
typedef long long LL;
 
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
 
const int N = 500005;
struct Edge{ 
    int to[N << 1], nxt[N << 1], head[N], En;
    inline void add_edge(int u,int v) {
        ++En; to[En] = v, nxt[En] = head[u]; head[u] = En;
        ++En; to[En] = u, nxt[En] = head[v]; head[v] = En;
    }
} G1, G2;
int dfn[N], low[N], sk[N], dis[N], dep[N], f[N][20], a[N];
int top, num, Index, TreeIndex, n;
 
void init() {
    top = Index = TreeIndex = G1.En = G2.En = 0;
    memset(G1.head, 0, sizeof(G1.head));
    memset(G2.head, 0, sizeof(G2.head));
    memset(dfn, 0, sizeof(dfn));
    memset(dep, 0, sizeof(dep));
    memset(dis, 0, sizeof(dis));
    memset(f, 0, sizeof(f));
    memset(low, 0, sizeof(low));
}
void tarjan(int u) {
    dfn[u] = low[u] = ++Index; sk[++top] = u;
    for (int i = G1.head[u]; i; i = G1.nxt[i]) {
        int v = G1.to[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                num ++; 
                do { G2.add_edge(sk[top --], num); } while (sk[top + 1] != v);
                G2.add_edge(num, u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
void dfs(int u) {
    dfn[u] = ++TreeIndex;
    dis[u] = dis[f[u][0]] + (u <= n);
    dep[u] = dep[f[u][0]] + 1;
    for (int i = 1; i <= 19; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = G2.head[u]; i; i = G2.nxt[i]) {
        int v = G2.to[i];
        if (v != f[u][0]) f[v][0] = u, dfs(v);
    }
}
int LCA(int u,int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int i = 19; ~i; --i) if ((d >> i) & 1) u = f[u][i];
    if (u == v) return u;
    for (int i = 19; ~i; --i) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
bool cmp(int a,int b) { return dfn[a] < dfn[b]; }
void query() {
    int k = read();
    for (int i = 1; i <= k; ++i) a[i] = read();
    int rt = a[1], ans = 0;
    sort(a + 1, a + k + 1, cmp);
    for (int i = 1; i <= k; ++i) {
        int x = a[i], y = a[i == k ? 1 : i + 1], z = LCA(x, y);
        if (dep[z] < dep[rt]) rt = z;
        ans += dis[x] + dis[y] - (dis[z] << 1);
    }
    printf("%d
", ans / 2 - k + (rt <= n));
}
void solve() {
    init();
    n = num = read();int m = read();
    for (int i = 1; i <= m; ++i) G1.add_edge(read(), read());
    tarjan(1);
    memset(dfn, 0, sizeof(dfn));
    dfs(1);
    int Q = read();
    while (Q --) query();   
}
int main() {
    for (int T = read(); T --; solve());
    return 0;
}