题解 P4606 【[SDOI2018]战略游戏】
看到这个题目的时候我惊了
这不是把我的 road 的询问点数从两个改成
所以这算不算我押中了 SDOI2018 的题目呀
首先使用 Tarjan 算法建出圆方树，然后答案就是 圆方树 上包含所有关键点的最少点数联通块 的圆点数量 减去 关键点的数量
为了方便，我们设圆点的权值设为 1 ，方点的权值为 0 ，将点权放到这个点与其父节点的边上
搞出树上的 DFS 序，将询问的关键点按照 DFS 序排序，求出排序之后的相邻关键点在树上路径的权值之和再加上排序之后第一个关键点与最后一个关键点在树上的路径权值之和，将其除以 2 就是圆方树上包含所有关键点的最少点数联通块的边权值和，转化为点权之和需要加上联通块根节点(也就是排序之后第一个关键点与最后一个关键点的LCA)的权值，最后减去关键点数量即可
时间复杂度:
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define DEBUG(args...) fprintf(stderr, args)
typedef long long LL;
#define FOR(i, l, r) for(int i = (l), i##_end = (r); i <= i##_end; ++i)
#define REP(i, l, r) for(int i = (l), i##_end = (r); i < i##_end; ++i)
#define DFR(i, l, r) for(int i = (l), i##_end = (r); i >= i##_end; --i)
#define DRP(i, l, r) for(int i = (l), i##_end = (r); i > i##_end; --i)
template<class T>T Min(const T &a, const T &b) {return a < b ? a : b;}
template<class T>T Max(const T &a, const T &b) {return a > b ? a : b;}
template<class T>bool Chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T>bool Chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
class fast_input {
private:
static const int SIZE = 1 << 15 | 1;
char buf[SIZE], *front, *back;
void Next(char &c) {
if(front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
c = front == back ? (char)EOF : *front++;
}
public :
template<class T>void operator () (T &x) {
char c, f = 1;
for(Next(c); !isdigit(c); Next(c)) if(c == '-') f = -1;
for(x = 0; isdigit(c); Next(c)) x = x * 10 + c - '0';
x *= f;
}
void operator () (char &c, char l = 'a', char r = 'z') {
for(Next(c); c > r || c < l; Next(c)) ;
}
}input;
const int SN = 200000 + 47;
const int LOGN = 18;
const int INF = 0x3f3f3f3f;
std::vector<int> graph[SN], tree[SN];
int low[SN], dfn[SN], rank, vis[SN], stack[SN], *top;
int f[SN][LOGN], deep[SN], dis[SN], cp, kp[SN], ckp;
int n;
void Clear();
void Tarjan(int, int);
void DFS(int);
int LCA(int, int);
int Dis(int, int);
int main() {
#ifdef Cai
freopen("s.in", "r", stdin);
#endif
int x, y, z, m, cases, q;
input(cases);
while(cases--) {
Clear(), input(n), input(m), cp = n;
FOR(i, 1, m) {
input(x), input(y);
graph[x].push_back(y);
graph[y].push_back(x);
}
Tarjan(1, -1);
deep[1] = 0, dis[1] = 0, rank = 0, DFS(1);
input(q);
while(q--) {
input(ckp);
REP(i, 0, ckp) input(kp[i]);
std::sort(kp, kp + ckp, [](int x, int y) {return dfn[x] < dfn[y];});
x = 0, kp[ckp] = kp[0];
REP(i, 0, ckp) x += Dis(kp[i], kp[i + 1]);
printf("%d\n", x / 2 - ckp + (LCA(kp[0], kp[ckp - 1]) <= n));
}
}
return 0;
}
void Clear() {
top = stack, rank = 0;
FOR(i, 1, n) graph[i].clear();
FOR(i, 1, cp) tree[i].clear(), dfn[i] = 0;
}
void Tarjan(int x, int y) {
dfn[x] = low[x] = ++rank, vis[x] = 1, *++top = x;
for(auto v : graph[x]) {
if(v == y || dfn[v] > dfn[x]) continue;
if(!dfn[v]) Tarjan(v, x), Chkmin(low[x], low[v]);
else if(vis[v]) {Chkmin(low[x], dfn[v]); continue;}
if(low[v] == dfn[x]) {
++cp, tree[x].push_back(cp);
while(*top != v) vis[*top] = 0, tree[cp].push_back(*top), --top;
tree[cp].push_back(v), vis[v] = 0, --top;
}
else if(low[v] > dfn[x])
tree[x].push_back(v), --top, vis[v] = 0;
}
}
void DFS(int x) {
dfn[x] = ++rank;
for(auto v : tree[x]) {
deep[v] = deep[x] + 1, dis[v] = dis[x] + (v <= n), f[v][0] = x;
REP(i, 1, LOGN) f[v][i] = f[f[v][i - 1]][i - 1];
DFS(v);
}
}
int LCA(int x, int y) {
if(deep[x] < deep[y]) std::swap(x, y);
for(int d = deep[x] - deep[y], i = 0; i < LOGN; ++i)
if(d >> i & 1)
x = f[x][i];
if(x == y) return x;
DFR(i, LOGN - 1, 0) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int Dis(int x, int y) {
int t = LCA(x, y);
return dis[x] + dis[y] - 2 * dis[t];
}