自动搬运

查看原文

来自洛谷，原作者为

	wyw666 底边。

搬运于2025-08-24 21:59:06，当前版本为作者最后更新于2021-08-16 10:23:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

原题传送门

对官方题解的详细解析

本题解源于官方题解，没有用到树剖、圆方树，并加入少量易于理解（或许）的修改，对像我这样的蒟蒻较为友好。

尽管这道毒瘤题还是卡了我十几遍提交

简单翻译题意：给定一个无向图，询问断开某条边或某个点后，另外两点是否连通。

首先给出样例的 dfs 树作为参考（不同方法建出的树形态有所不同），黑边为树边，红边为回边。

提示：本题中默认将 a，b，g1，g2排序，其中 $dfn(a) \le dfn(b),dfn(g1) \le dfn(g2)$

询问 1

不难发现一个性质：若 g1、g2 在 dfs 树中不相邻，则直接连接 g1 和 g2 的边一定为回边。

• 判定：观察 g1 、g2 在 dfs 树中的深度是否相差 1 。

• 利用：如果是回边，则至少有两条路连接 g1 、 g2 。因此 g1 到 g2 的路断开后不影响原图的连通性。

经过如上的特判后，我们可以将 g1 、 g2 限制为一上一下相邻的两条边。

再分情况讨论：

a 包含 b：

首先得出 g1，g2 能影响 a，b 的必要条件：g1 在 a 的子树内，b 在 g2 的子树内。

当然，这样还不够，因为 g2 到 b 的某个点可能有回边指向 a 到 g1 的某个点：

如何判断？

我们想到了 tarjan 的 low。

假如 g2 的 low 小于等于 g1 的 dfn ，则说明 a，b 仍然联通。

a 不包含 b：

必要条件： g1，g2 在 a，b 的路径上，具体实现可以用 lca 。

进一步分析可以得出充分必要条件：即使断开了 g1，g2 ，若 a 与 lca(a, b) 联通，且 b 与 lca(a, b) 联通，则 a，b 仍然联通。

证明：假设 a 不与 lca(a, b) 联通，可知 g1，g2在 lca(a, b) 到 a 的路径上，且 g2 到 a 的路径上没有回边能通向 g1 及更高的点。

因为无向图的 dfs 树中不存在横叉边，所以 a 与 b 之间绝无通路。

对 b 同理。

因此，我们可以将该询问拆成两个询问： (a, lca(a,b), g1, g2) 和 （b, lca(a,b), g1, g2）。

询问 2

同样是分是否包含进行讨论。

a 包含 b：

设 c 到 b 的 related_child 为 c 到 b 的路径上（不是回边），与 c 直接相连的点。

如询问 1 一样判断 related_child 的 low 即可。

a 不包含 b：

首先需要满足 c 在 a，b 的路径上，取 a，b 的 related_child 拆成两个询问即可。

问题

• 如何判断某个点在另一个点的子树内？

  在 dfs 的过程中，一棵树的根节点必然比叶节点入栈早、出栈晚。

  trajan 的过程中记下进入该点的时间戳 dfn 及离开该点的时间戳 finish ，对比即可。

• 如何找 related_child ？

  两种方法：一种是遍历每个儿子并判断是否包含另一节点，一种是直接倍增上去，我用了第二种。

代码实现

//请使用C++11编译
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1000001;
struct edge
{
	int to, next;
};
int head[N];
vector<edge> E;
void insert(int u, int v)
{
	E.push_back({ v,head[u] });
	head[u] = E.size() - 1;
}
int dfn[N], finish[N], low[N], now;
int d[N], fa[N][20], lg[N];
void tarjan(int u, int f)
{
	d[u] = d[f] + 1;
	fa[u][0] = f;
	for (int i = 1; i <= lg[d[u]]; i++)fa[u][i] = fa[fa[u][i - 1]][i - 1];
	dfn[u] = low[u] = ++now;
	for (int i = head[u]; ~i; i = E[i].next)
	{
		int v = E[i].to;
		if (!dfn[v])
		{
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}
		else if (v != f)low[u] = min(low[u], dfn[v]);
	}
	finish[u] = ++now;
}
int lca(int x, int y)
{
	if (d[x] < d[y])swap(x, y);
	while (d[x] > d[y])x = fa[x][lg[d[x] - d[y]] - 1];
	if (x == y)return x;
	for (int i = lg[d[x]] - 1; i >= 0; i--)
	{
		if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}
int n, m, q;

// 判断节点 f 是否包含节点 a
bool contains(int f, int a)
{
	return dfn[f] <= dfn[a] && finish[f] >= finish[a];
}

// 查找 f 到 a （ f 包含 a ）的路径上，与 f 直接相连的点
int find_related_child(int f, int a)
{
	int df = d[f] + 1;
	while (d[a] > df)a = fa[a][lg[d[a] - df] - 1];
	return a;
}
bool query1(int a, int b, int g1, int g2)
{
	if (a == b)return true;
	if (dfn[a] > dfn[b])swap(a, b);
	if (dfn[g1] > dfn[g2])swap(g1, g2);
	if (d[g2] != d[g1] + 1)return true; // g1 -> g2 为回边
	if (contains(a, b)) // a 包含 b
	{
		if (contains(a, g1) && contains(g2, b))
		{
			return low[g2] <= dfn[g1];
		}
		else return true;
	}
	else
	{
		int l = lca(a, b);
		return query1(a, l, g1, g2) && query1(b, l, g1, g2);
	}
}
bool query2(int a, int b, int c)
{
	if (a == b)return a != c;
	if (a == c || b == c)return false;
	if (dfn[a] > dfn[b])swap(a, b);
	if (contains(a, b)) // a 包含 b
	{
		if (contains(a, c) && contains(c, b))
		{
			return low[find_related_child(c, b)] < dfn[c]; //注意这里是小于
		}
		else return true;
	}
	else
	{
		int l = lca(a, b);
		if (contains(l, c) && (contains(c, a) || contains(c, b)))
		{
			return query2(a, fa[l][0], c) && query2(b, fa[l][0], c);
		}
		else return true;
	}
}
int main()
{
	memset(head, -1, sizeof head);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	for (int i = 1, u, v; i <= m; i++)
	{
		cin >> u >> v;
		insert(u, v);
		insert(v, u);
	}
	tarjan(1, 1);
	cin >> q;
	for (int i = 1, a, b, c, d; i <= q; i++)
	{
		cin >> a;
		if (a == 1)
		{
			cin >> a >> b >> c >> d;
			cout << (query1(a, b, c, d) ? "yes" : "no") << endl;
		}
		else
		{
			cin >> a >> b >> c;
			cout << (query2(a, b, c) ? "yes" : "no") << endl;
		}
	}
	return 0;
}