【题解】LOJ 2562 「SDOI2018」战略游戏

Problem

给定一个 $n$ 个点 $m$ 条边的无向图,每次给定一个集合,问能将集合割开的点有多少

Thought

能将集合割开的点必然是割点,并且该点必然在集合中的点的路径上,这样就能保证能将路径两端的点割开

求路径上的割点只需要使用圆方树即可,再加上利用虚树的思想在圆方树上统计圆点个数

最后减去集合中的点的个数,因为这些点不能作为割点

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int M = 200010;
struct Graph {
    int f[M << 2], t[M << 2], n[M << 2];
    int head[N << 1], tot;
    void addedge(int u, int v) {
        ++ tot;
        f[tot] = u; t[tot] = v;
        n[tot] = head[u];
        head[u] = tot;
    }
    void clear() {
        memset(head, 0, sizeof(head));
        tot = 0;
    }
}G, H;
int sta[M << 2], low[N], dfn[N], DFN, top, cnt;
int n, m, q, belong[N];
int fa[N << 1][21], key[N << 1], dep[N << 1];
int que[N];

void clear() {
    memset(fa, 0, sizeof(fa));
    memset(dep, 0, sizeof(dep));
    memset(key, 0, sizeof(key));
    G.clear(); H.clear();
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(belong, 0, sizeof(belong));
    cnt = DFN = 0;
}

void dfs(int x) {
    low[x] = dfn[x] = ++ DFN;
    for(int i = G.head[x]; i; i = G.n[i]) {
        int to = G.t[i];
        if(!dfn[to]) {
            sta[++ top] = i;
}            dfs(to);
            low[x] = min(low[x], low[to]);
            if(low[to] == dfn[x]) {
                ++ cnt;
                H.addedge(x, n + cnt);
                H.addedge(n + cnt, x);
                belong[x] = cnt;
                H.addedge(to, n + cnt);
                H.addedge(n + cnt, to);
                belong[to] = cnt;
                for(; sta[top] != i; sta[top --] = 0) {
                    if(belong[G.f[sta[top]]] != cnt) {
                        H.addedge(G.f[sta[top]], n + cnt);
                        H.addedge(n + cnt, G.f[sta[top]]);
                        belong[G.f[sta[top]]] = cnt;
                    }
                    if(belong[G.t[sta[top]]] != cnt) {
}                        H.addedge(G.t[sta[top]], n + cnt);
                        H.addedge(n + cnt, G.t[sta[top]]);
                        belong[G.t[sta[top]]] = cnt;
                    }
                }
                sta[top --] = 0;
            }
        }
        else if(dfn[to] < dfn[x]) {
            sta[++ top] = i;
            low[x] = min(low[x], dfn[to]);
        }
    }
}
void DFS(int x) {
    dfn[x] = ++ DFN; dep[x] = dep[fa[x][0]] + 1;
    key[x] = key[fa[x][0]] + (x <= n);
    for(int i = 1; i <= 20; ++ i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(int i = H.head[x]; i; i = H.n[i]) {
        int to = H.t[i];
        if(to == fa[x][0]) continue;
        fa[to][0] = x;
        DFS(to);
    }
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 20; i >= 0; -- i)
        if(dep[fa[a][i]] >= dep[b])
            a = fa[a][i];
    if(a == b) return a;
    for(int i = 20; i >= 0; -- i)
        if(fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}
int query(int a, int b) {
    if(!b) return key[a] - key[fa[a][0]];
    int ans = 0;
    for(int i = 20; i >= 0; -- i)
        if(dep[fa[a][i]] >= dep[b]) {
            ans += key[a] - key[fa[a][i]];
            a = fa[a][i];
        }
    return ans;
}

bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}

void work() {
    clear();
    n = read(); m = read();
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        G.addedge(u, v);
        G.addedge(v, u);
    }
    dfs(1);
    memset(dfn, 0, sizeof(dfn)); DFN = 0;
    DFS(1);
    q = read();
    for(int i = 1; i <= q; ++ i) {
        int S = read(), sum = 0;
        for(int j = 1; j <= S; ++ j)
            que[j] = read();
        sort(que + 1, que + S + 1, cmp);
        int L = que[1];
        for(int j = 2; j <= S; ++ j)
            L = lca(L, que[j]);
        sta[++ top] = L;
        for(int j = 1; j <= S; ++ j) {
            if(que[j] == sta[top]) continue;
            int l = lca(que[j], sta[top]);
            if (l != sta[top]) {
                while(top >= 2 && dep[l] <= dep[sta[top - 1]]) {
                    sum += query(sta[top], sta[top - 1]);
                    sta[top --] = 0;
                }
                if(l != sta[top - 1]) {
                    sum += query(sta[top], l);
                    sta[top] = l;
                }
                else {
                    sum += query(sta[top], sta[top - 1]);
                    sta[top --] = 0;
                }
            }
            sta[++ top] = que[j];
        }
        while(top) {
            sum += query(sta[top], sta[top - 1]);
            sta[top --] = 0;
        }
        printf("%d\n", sum - S);
    }
}
int main() {
    int t = read();
    while(t --) work();
    return 0;
}
Comments

添加新评论