P4334 [COI2007] Policija 题解
原题传送门
对官方题解的详细解析
本题解源于官方题解，没有用到树剖、圆方树，并加入少量易于理解（或许）的修改，对像我这样的蒟蒻较为友好。
尽管这道毒瘤题还是卡了我十几遍提交
简单翻译题意：给定一个无向图，询问断开某条边或某个点后，另外两点是否连通。
首先给出样例的 dfs 树作为参考（不同方法建出的树形态有所不同），黑边为树边，红边为回边。
提示：本题中默认将 a，b，g1，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;
}