题意
给定一个 $n$ 个点，$m$ 条边的无向图。$q$ 次询问，每次询问给出 $a, b, c$，问能否找出一条从 $a$ 到 $b$ 的路径，中途不经过 $c$ 点。
题解
首先对这个图建出一个圆方树。
如果 $c$ 不是割点那肯定有满足条件的路径。
否则判断 $c$ 点是否在圆方树上 $a$ 到 $b$ 的路径中，树剖实现。
class Block_Forest_Builder {
using Ty = long long;
vector<vector<Ty>> G, T;
vector<Ty> dfn, low, stk;
size_t cnt;
void Tarjan(Ty u) {
low[u] = dfn[u] = cnt++;
stk.push_back(u);
for (auto& v : G[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] == dfn[u]) {
T.push_back(vector<Ty>());
for (long long x = -1; x != v; stk.pop_back()) {
x = stk.back();
T[T.size() - 1].push_back(x);
T[x].push_back(T.size() - 1);
}
T[T.size() - 1].push_back(u);
T[u].push_back(T.size() - 1);
}
} else low[u] = min(low[u], dfn[v]);
}
}
public:
Block_Forest_Builder() = default;
vector<vector<Ty>>& operator()(vector<vector<Ty>>& g) {
G.swap(g);
cnt = 0;
low = dfn = vector<Ty>(G.size(), 0);
T.resize(G.size());
for (size_t i = 0; i < G.size(); ++i) {
if (!dfn[i]) { Tarjan(i); stk.clear(); }
}
G.swap(g);
return T;
}
} Block_Forest;
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, m, q; bin >> n >> m >> q;
vector<vector<tp>> g(n + 1);
while (m--) {
tp u, v; bin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<vector<tp>> t = Block_Forest(g);
n = t.size();
vector<tp> w(n + 1), dep(n + 1), f(n + 1), hson(n + 1), s(n + 1), top(n + 1), dfn(n + 1);
auto dfs1 = [&](auto& _, tp x) -> void {
dep[x] = dep[f[x]] + 1;
s[x] = 1;
for (auto& i : t[x]) {
if (i == f[x]) continue;
f[i] = x;
_(_, i);
s[x] += s[i];
if (s[i] > s[hson[x]]) hson[x] = i;
}
};
auto dfs2 = [&](auto& _, tp x, tp h) -> void {
static tp cnt = 0;
dfn[x] = ++cnt;
top[x] = h;
if (!hson[x]) return;
_(_, hson[x], h);
for (auto& i : t[x]) {
if (i != f[x] && i != hson[x]) _(_, i, i);
}
};
auto query = [&](tp x, tp y, tp z) -> bool {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
if (dfn[top[x]] <= dfn[z] && dfn[z] <= dfn[x]) return false;
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
if (dfn[x] <= dfn[z] && dfn[z] <= dfn[y]) return false;
return true;
};
dfs1(dfs1, 1);
dfs2(dfs2, 1, 1);
while (q--) {
tp x, y, z; bin >> x >> y >> z;
bin << (query(x, y, z) ? "YES\n" : "NO\n");
}
}