自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:29:02，当前版本为作者最后更新于2023-03-29 21:44:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到“不能经过 Tom 所在的点”，不难想到割点。

对于 Tom 而言，首先可以注意到一种简单的策略：

• 逼着 Jerry 往某个子连通块里走。

现在来具体地描述这个“逼”的过程。

我们发现在这种策略下，当 Tom 获胜时，Tom 初始一定处于一个割点，每一步都会走进一个让 Jerry 活动范围更小的割点，从而 Jerry 被迫在一个更小的子连通块内走，最终被抓到。

考虑建出原图的圆方树，现在把 $a$ 提起来当圆方树的根，设 $b$ 在换根后的树上位于 $a$ 的 $b'$ 子树，则 $b$ 一开始只能在 $b'$ 子树内的圆点内活动。

现在 Tom 想要把当前位置 $p$ 移到一个 $q$，满足：

• $q$ 为割点或可以在 $q$ 抓到 Jerry。
• 圆方树上 $q$ 在 $p$ 子树中。
• 原图上 $p, q$ 有边。

这个几个条件同时也告诉我们 $q$ 一定是 $p$ 所在的某个点双的除 $p$ 以外的点（称此为条件 $P$），这样才可能满足距离为 $1$。

注意到 Jerry 在第一次操作时可以在任何一个符合条件的点，所以 $\forall u \in subtree_{b'}$，都需要满足在按照上面的方式操作后，存在一种方案使得 Tom 最终 $p = u$。

也就是说，$\forall p \in subtree_{b'}$ 且 $q$ 满足条件 $P$，$p, q$ 在原图上有边。

我们肯定不可能把每个 $a$ 拿出来当根讨论，于是考虑换根 dp，预处理 $f_u, g_u$ 表示以 $1$ 为根时内 / 外子树是否满足上述条件，回答询问时讨论一下 $b$ 是否在 $a$ 的子树中即可。

但因为 $a$ 一开始可能不是割点，一开始 Jerry 可以处在一个任意点。

注意到此时 Tom 并非必败，因为此时 Tom 还有另一种策略：

• 走到一个点 $r$，满足以 $r$ 为根，无论 Jerry 位于哪个非 $r$ 点，都可以按照上述方式被抓到。

在换根 dp 结束后看一下有没有点 $u$ 满足 $f_u = g_u = \operatorname{true}$，如果有则答案为全 Yes，否则该策略一定不可行。

综上，时间复杂度为 $O(m + (n + q) \log n)$。

代码：

#include <iostream>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

typedef struct {
	int nxt;
	int end;
} Edge;

int cnt1 = 0, cnt2 = 0;
int head1[100007], dfn[100007], low[100007], head2[200007], depth[200007], in[200007], fa[200007][27], out[200007];
bool vis[100007], dp1[200007], dp2[200007];
Edge edge1[200007], edge2[400007];
set<int> se1;
stack<int> stk;
set<int> se2[100007];

inline void add_edge1(int start, int end){
	cnt1++;
	edge1[cnt1].nxt = head1[start];
	head1[start] = cnt1;
	edge1[cnt1].end = end;
}

inline void add_edge2(int start, int end){
	cnt2++;
	edge2[cnt2].nxt = head2[start];
	head2[start] = cnt2;
	edge2[cnt2].end = end;
}

void tarjan(int u, int father, int n, int &id, int &bcc_cnt){
	int son_cnt = 0;
	dfn[u] = low[u] = ++id;
	vis[u] = true;
	stk.push(u);
	for (register int i = head1[u]; i != 0; i = edge1[i].nxt){
		int x = edge1[i].end;
		if (!vis[x]){
			son_cnt++;
			tarjan(x, u, n, id, bcc_cnt);
			low[u] = min(low[u], low[x]);
			if (low[x] >= dfn[u]){
				int pos = ++bcc_cnt + n, cur;
				add_edge2(pos, u);
				add_edge2(u, pos);
				do {
					cur = stk.top();
					stk.pop();
					add_edge2(pos, cur);
					add_edge2(cur, pos);
				} while (cur != x);
			}
		} else {
			low[u] = min(low[u], dfn[x]);
		}
	}
	if (father == 0 && son_cnt == 0){
		int pos = ++bcc_cnt + n;
		add_edge2(pos, u);
		add_edge2(u, pos);
	}
}

void dfs1(int u, int father, int n, int &id){
	int t;
	depth[u] = depth[father] + 1;
	t = log2(depth[u]);
	in[u] = ++id;
	fa[u][0] = father;
	for (register int i = 1; i <= t; i++){
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	dp1[u] = true;
	for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
		int x = edge2[i].end;
		if (x != father){
			dfs1(x, u, n, id);
			dp1[u] &= dp1[x];
			if (u > n) dp1[u] &= se2[father].count(x);
		}
	}
	out[u] = id;
}

void dfs2(int u, int n){
	int cnt1 = 0, size;
	se1.clear();
	if (fa[u][0] != 0) se1.insert(fa[u][0]);
	for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
		int x = edge2[i].end;
		if (x != fa[u][0]){
			se1.insert(x);
			if (!dp1[x]) cnt1++;
		}
	}
	size = se1.size();
	for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
		int x = edge2[i].end;
		if (x != fa[u][0]){
			dp2[x] = dp2[u] && (cnt1 == 0 || (cnt1 == 1 && !dp1[x]));
			if (u > n){
				int cnt2 = 0;
				for (register int j = head1[x]; j != 0; j = edge1[j].nxt){
					if (se1.count(edge1[j].end)) cnt2++;
				}
				dp2[x] &= cnt2 + 1 == size;
			}
		}
	}
	for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
		int x = edge2[i].end;
		if (x != fa[u][0]) dfs2(x, n);
	}
}

inline bool check(int u, int v){
	return in[u] <= in[v] && in[v] <= out[u];
}

inline int jump(int u, int k){
	for (register int i = 0; (1 << i) <= k; i++){
		if (k >> i & 1) u = fa[u][i];
	}
	return u;
}

int main(){
	int n, m, q, dfn_id1 = 0, bcc_cnt = 0, dfn_id2 = 0;
	cin >> n >> m >> q;
	for (register int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		se2[x].insert(y);
		se2[y].insert(x);
		add_edge1(x, y);
		add_edge1(y, x);
	}
	tarjan(1, 0, n, dfn_id1, bcc_cnt);
	dfs1(1, 0, n, dfn_id2);
	dp2[1] = true;
	dfs2(1, n);
	for (register int i = 1; i <= n; i++){
		if (dp1[i] && dp2[i]){
			for (register int j = 1; j <= q; j++){
				cout << "Yes" << endl;
			}
			return 0;
		}
	}
	for (register int i = 1; i <= q; i++){
		int a, b;
		cin >> a >> b;
		if (!check(a, b)){
			if (dp2[a]){
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		} else if (dp1[jump(b, depth[b] - depth[a] - 1)]){
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	return 0;
}