自动搬运

查看原文

来自洛谷，原作者为

	Caii **

搬运于2025-08-24 22:01:53，当前版本为作者最后更新于2018-05-16 20:17:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到这个题目的时候我惊了

这不是把我的 road 的询问点数从两个改成 $k$ 个吗，所以如果你写过我公开赛的这个题你就可以 SDOI2018 考场上拿到至少 45 分了

所以这算不算我押中了 SDOI2018 的题目呀

首先使用 Tarjan 算法建出圆方树，然后答案就是 圆方树 上包含所有关键点的最少点数联通块 的圆点数量 减去 关键点的数量

为了方便，我们设圆点的权值设为 1 ，方点的权值为 0 ，将点权放到这个点与其父节点的边上

搞出树上的 DFS 序，将询问的关键点按照 DFS 序排序，求出排序之后的相邻关键点在树上路径的权值之和再加上排序之后第一个关键点与最后一个关键点在树上的路径权值之和，将其除以 2 就是圆方树上包含所有关键点的最少点数联通块的边权值和，转化为点权之和需要加上联通块根节点(也就是排序之后第一个关键点与最后一个关键点的LCA)的权值，最后减去关键点数量即可

时间复杂度:$O(N\log N)$

#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];
}