yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P4606 战略游戏 题解

发表于 更新于 分类于

P4606 战略游戏 题解

题面

题目链接

解法

圆方树上圆方果

圆方树下你和我

圆方树前建虚树

欢乐多又多 /kk

看到$\sum|S|$于是开始套路地想到虚树。

但是给定的是一个无向图不是一棵树啊……

所以要想办法把图转化成一棵树，这样的数据结构叫做圆方树。

这里假设你已经学会圆方树了

考虑圆方树的性质。显然对于一对节点$(u, v)$，它们在圆方树上的路径中的圆点（不包括自身）就是删掉后能使得$u$和$v$不连通的点。因为根据圆方树的性质，所有和同一个方点连边的圆点都在同一个双联通分量里，去掉一个方点不会改变图的连通性。而那些和多个方点连边的圆点都可以成为这些方点的割点，去掉后图的连通性就改变了。

于是答案就是所有特殊节点之间的路径并上圆点数量减去$|S|$。

思路还是很简单的，主要是代码中的亿点点细节。比如说MAXN要开两倍大小（因为有圆方树）、统计答案不要把虚树的所有边权都加上（因为虚树要建立节点$1$而有时节点$1$并不出现在路径并中）以及多测要清空dfn数组等等。

时间复杂度$O(n \log n)$（感觉常数巨大无比）。调了两天。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/**
 * @file:           P4606.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4606
*/
// #pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 4e5 + 10;
const int MAXM = 8e5 + 10;
const int LOGN = 20;
const int INFL = 0x3f3f3f3f3f3f3f3f;
struct Graph {
    struct Edge {
        int v, w;
    } edge[MAXM];
    int head[MAXN], nxt[MAXM], tot;
    void addedge(int u, int v, int w = 1) {
        edge[tot] = {v, w};
        nxt[tot] = head[u];
        head[u] = tot++;
    }
};
int n, m, q, k, dfc, top, bcc, idn;
int s[MAXN], dfn[MAXN], low[MAXN], sta[MAXN];
int id[MAXN], dep[MAXN], fa[MAXN][LOGN];
bool tag[MAXN];
Graph g, tr, vtr;
void clear() {
    g.tot = tr.tot = vtr.tot = 0;
    // ##sb-mistakes## 多测不清空，爆零两行泪/kk 多测`dfn`数组记得清空啊
    memset(dfn, 0, sizeof(dfn));
    memset(g.head, -1, sizeof(g.head));
    memset(tr.head, -1, sizeof(tr.head));
    memset(vtr.head, -1, sizeof(vtr.head));
}
void tarjan(int u) {
    dfn[u] = low[u] = ++dfc;
    sta[++top] = u;
    for (int i = g.head[u]; ~i; i = g.nxt[i]) {
        int v = g.edge[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (dfn[u] == low[v]) {
                ++bcc;
                for (int x = 0; x != v; --top) {
                    x = sta[top];
                    tr.addedge(bcc, x);
                    tr.addedge(x, bcc);
                }
                tr.addedge(bcc, u);
                tr.addedge(u, bcc);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
void build(int u, int f) {
    id[u] = ++idn;
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for (int i = 1; i < LOGN; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = tr.head[u]; ~i; i = tr.nxt[i])
        if (tr.edge[i].v != f)
            build(tr.edge[i].v, u);
}
int lca(int u, int v) {
    if (dep[u] < dep[v])
        swap(u, v);
    int t = dep[u] - dep[v];
    for (int i = LOGN - 1; ~i; --i)
        if ((t >> i) & 1)
            u = fa[u][i];
    if (u == v)
        return u;
    for (int i = LOGN - 1; ~i; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
void add_vedge(int u, int v) {
    int w = ((dep[v] - dep[u]) & 1) ? ((dep[v] - dep[u]) / 2) : ((dep[v] - dep[u]) / 2 - (v <= n));
    vtr.addedge(u, v, w);
}
void build_vtr() {
    sort(s + 1, s + k + 1, [](int x, int y) {
        return id[x] < id[y];
    });
    sta[top = 1] = 1, vtr.head[1] = -1, vtr.tot = 0;
    for (int i = 1; i <= k; ++i) {
        if (s[i] == 1)
            continue;
        int l = lca(sta[top], s[i]);
        if (l < 1 || l > bcc)
            lca(sta[top], s[i]);
        while (id[l] <= id[sta[top - 1]])
            add_vedge(sta[top - 1], sta[top]), --top;
        if (sta[top] != l)
            vtr.head[l] = -1, add_vedge(l, sta[top]), sta[top] = l;
        vtr.head[s[i]] = -1, sta[++top] = s[i];
    }
    for (int i = 1; i < top; ++i)
        add_vedge(sta[i], sta[i + 1]);
}
int calc(int u, bool tg) {
    tg |= tag[u];
    int ret = 0, sum = (u <= n), chd = 0;
    for (int i = vtr.head[u]; ~i; i = vtr.nxt[i]) {
        int v = vtr.edge[i].v, w = vtr.edge[i].w;
        sum += w, ret += calc(v, tg), chd++;
    }
    return ret + ((tg || chd > 1) ? sum : 0);
}
void solve() {
    read(n), read(m);
    bcc = n, dfc = idn = 0, clear();
    for (int i = 1; i <= m; ++i) {
        int u, v;
        read(u), read(v);
        g.addedge(u, v);
        g.addedge(v, u);
    }
    top = 0, tarjan(1), build(1, 0);
    read(q);
    while (q--) {
        read(k);
        for (int i = 1; i <= k; ++i)
            read(s[i]), tag[s[i]] = true;
        build_vtr();
        write(calc(1, false) - k), putchar('\n');
        for (int i = 1; i <= k; ++i)
            tag[s[i]] = false;
    }
}
signed main() {
    int t;
    read(t);
    while (t--)
        solve();
    return 0;
}