luogu4606 [SDOI2018]战略游戏

题目描述

省选临近,放飞自我的小 $Q$ 无心刷题,于是怂恿小 $C$ 和他一起颓废,玩起了一款战略游戏。

这款战略游戏的地图由 $n$ 个城市以及 $m$ 条连接这些城市的双向道路构成,并且从任意一个城市出发总能沿着道路走到任意其他城市。

现在小 $C$ 已经占领了其中至少两个城市,小 $Q$ 可以摧毁一个小 $C$ 没占领的城市,同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 $C$ 占领的城市 $u$ 和 $v$,使得从 $u$ 出发沿着道路无论如何都不能走到 $v$,那么小 $Q$ 就能赢下这一局游戏。

小 $Q$ 和小 $C$ 一共进行了 $q$ 局游戏,每一局游戏会给出小 $C$ 占领的城市集合 $S$,你需要帮小 $Q$ 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

输入格式

第一行包含一个正整数 T,表示测试数据的组数

对于每组测试数据

第一行是两个整数 $n$ 和 $m$ ,表示地图的城市数和道路数

接下来 $m$ 行,每行包含两个整数 $u$ 和 $v (1 \le u < v \le n)$,表示第 u 个城市和第 $v$ 个城市之间有一条道路,同一对城市之间可能有多条道路连接

第 $m + 1$ 是一个整数 $q$,表示游戏的局数,

接下来 $q$ 行,每行先给出一个整数 $|S| (2 \le |S| \le n)$,表示小 $C$ 占领的城市数量,然后给出 $|S|$ 个整数 $(1 \le s1 < s2$ $< ... <s|S| \le n)$,表示小 $C$ 占领的城市。

输出格式

对于每一局游戏,输出一行,包含一个整数,表示这一局游戏中有多少个城市在小 $Q$ 摧毁之后能够

让他赢下这一局游戏。

样例输入

2
7 6
1 2
1 3
2 4
2 5
3 6
3 7
3
2 1 2
3 2 3 4
4 4 5 6 7
6 6
1 2
1 3
2 3
1 4
2 5
3 6
4
3 1 2 3
3 1 2 6
3 1 5 6
3 4 5 6

样例输出

0
1
3
0
1
2
3

说明

$1 \le T \le 10$

$2 \le n \le 10^5$ 且$n-1\le m\le2×10^5$

$1 \le q \le 10^5$

对于每组测试数据,有 $∑|S| \le 2 × 10^5$

Subtasks

子任务 1 (30 分):对于每组测试数据,满足 $∑|S| \le 20$

子任务 2 (45 分):对于每一次询问,满足 $|S| = 2$

子任务 3 (25 分):没有任何附加的限制。


分析

好久没更博客了……退役前的最后一个月。

在一般图上删去某个点后使某些点不连通,发现跟割点似乎有点关系,可以想到建出圆方树,然后答案就是虚树上的所有圆点减去询问的圆点个数。

令方点的点权为$0$,圆点的点权为$1$,再把点权推到父边上,即转化为求虚树的边权和,再加上虚树根的点权。

虚树可以不用建出来,把询问的点按dfs序排序,然后对相邻的点两两做路径查询,再加上第一个点与最后一个点的路径和,然后除以二,就可以得到虚树的边权和。

代码

#include <bits/stdc++.h>

const int N = 4e5+50;
const int M = 1e6+50;
const int D = 22;

struct Graph {
    struct Edge {
        int to, nxt;
    } e[M<<1];
    int top, head[N<<1];

    Graph() {
        clear();
    }

    void clear() {
        top = 0;
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }

    void add2(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G, R;

int n, m;
int low[N], dfn[N], dfx;
std::stack<int> stk;
int rtop;
int w[N], sum[N], dep[N];
int a[N];
int anc[N][D];
int bin[D];

void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++dfx;
    w[u] = 1;
    stk.push(u);
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                R.add2(++rtop, u);
                while (!stk.empty()) {
                    int x = stk.top();
                    stk.pop();
                    R.add2(rtop, x);
                    if (x == v) break;
                }
            }
        } else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}

void clear() {
    G.clear();
    R.clear();
    while (!stk.empty())
        stk.pop();
    memset(dfn, 0, sizeof dfn);
    dfx = 0;
    memset(w, 0, sizeof w);
}

void dfs(int u, int fa) {
    dfn[u] = ++dfx;
    anc[u][0] = fa;
    for (int i = 1; i < D; i++)
        anc[u][i] = anc[anc[u][i-1]][i-1];
    sum[u] = sum[fa] + w[u];
    dep[u] = dep[fa] + 1;
    for (int i = R.head[u]; ~i; i = R.e[i].nxt) {
        int v = R.e[i].to;
        if (v == fa) continue;
        dfs(v, u);
    }
}

int getLca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    int delta = dep[u] - dep[v];
    for (int i = 0; i < D; i++)
        if (delta & bin[i]) u = anc[u][i];
    if (u == v) return u;
    for (int i = D-1; i >= 0; i--) {
        if (anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int pathSum(int u, int v) {
    int lca = getLca(u, v);
    return sum[u] + sum[v] - sum[lca] * 2;
}

bool cmp(int t1, int t2) {
    return dfn[t1] < dfn[t2];
}

int main() {
    bin[0] = 1;
    for (int i = 1; i < D; i++)
        bin[i] = bin[i-1] << 1;
    int T;
    scanf("%d", &T);
    while (T--) {
        clear();
        scanf("%d%d", &n, &m);
        rtop = n;
        for (int i = 1, u, v; i <= m; i++) {
            scanf("%d%d", &u, &v);
            G.add2(u, v);
        }
        tarjan(1, 0);
        dfx = 0;
        dfs(1, 0);
        int q;
        scanf("%d", &q);
        while (q--) {
            int cnt;
            scanf("%d", &cnt);
            for (int i = 1; i <= cnt; i++)
                scanf("%d", &a[i]);
            std::sort(a+1, a+cnt+1, cmp);
            a[cnt+1] = a[1];
            int ans = 0;
            for (int i = 1; i <= cnt; i++)
                ans += pathSum(a[i], a[i+1]);
            ans = ans / 2 + w[getLca(a[1], a[cnt])] - cnt;
            printf("%d\n", ans);
        }
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论