Tarjan 边双缩点 + Tarjan 离线 LCA

求一组 hack 数据或错误点。不胜感激。

#include <iostream>
#include <vector>

#define i64 long long
#define endl '\n'
#define qwq puts("fzy qwq ~");
using namespace std;
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)

const int N = 3e5 + 10;
const int M = 3e5 + 10;

int n, m, q;
int dfncnt, dcccnt;
int dfn[N], low[N], dcc[N];
int sum[N], siz[N];
bool b[M << 1];
pair<int, int> qry[N];

struct Graph
{
	struct Edge { int v, w, nxt; };
	Edge e[M << 1]; int h[N], tot = 1;
	inline void add(int u, int v, int w)
	{ e[++tot] = { v, w, h[u] }; h[u] = tot; }
} G, T;

namespace DSU
{
int fa[N];
inline void init(int n) { for (int i = 1; i <= n + 5; ++i) fa[i] = i; }
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int p, int q) { fa[q] = p; }
}
using namespace DSU;

namespace TarjanLCA
{

struct QryGraph
{
	struct QEdge { int v, nxt; };
	QEdge e[M << 1]; int h[N], tot = 1;
	inline void add(int u, int v)
	{ e[++tot] = { v, h[u] }; h[u] = tot; }
} Q;
bool vis[N]; int res[N << 1];
inline void tarjanLCA(int u)
{
	vis[u] = 1;
	for (int i = T.h[u]; i; i = T.e[i].nxt)
	{
		int v = T.e[i].v;
		if (vis[v]) continue;
		tarjanLCA(v); fa[v] = u;
	}
	for (int i = Q.h[u]; i; i = Q.e[i].nxt)
	{
		int v = Q.e[i].v;
		if (vis[v])
		{
			res[i] = find(v);
			if (i & 1) res[i + 1] = res[i];
			else       res[i - 1] = res[i];
		}
	}
}
inline int LCA(int i) { return res[i << 1]; }
} using namespace TarjanLCA;

inline void tarjan(int u, int ine)
{
	dfn[u] = low[u] = ++dfncnt;
	for (int i = G.h[u]; i; i = G.e[i].nxt)
	{
		int v = G.e[i].v;
		if (!dfn[v])
		{
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			if (dfn[u] < low[v]) b[i] = b[i ^ 1] = 1;
		}
		else if (i != (ine ^ 1))
			low[u] = min(low[u], dfn[v]);
	}
}
inline void dfs(int u)
{
	dcc[u] = dcccnt;
	for (int i = G.h[u]; i; i = G.e[i].nxt)
	{
		int v = G.e[i].v;
		if (dcc[v] == dcc[u]) siz[dcccnt] += G.e[i].w;
		if (!b[i] && !dcc[v])
			dfs(v), siz[dcccnt] += G.e[i].w;
	}
}

inline void rebuild()
{
	for (int u = 1; u <= n; ++u)
		for (int i = G.h[u]; i; i = G.e[i].nxt)
		{
			int v = G.e[i].v;
			if (dcc[u] != dcc[v])
				T.add(dcc[u], dcc[v], G.e[i].w);
		}
	rep (i, 1, dcccnt) sum[i] = siz[i];
}

inline void fix(int u, int fa)
{
	sum[u] += sum[fa];
	for (int i = T.h[u]; i; i = T.e[i].nxt)
	{
		int v = T.e[i].v;
		if (v == fa) continue;
		sum[v] += T.e[i].w; fix(v, u);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	rep (i, 1, m)
	{
		int u, v, w; cin >> u >> v >> w;
		G.add(u, v, w); G.add(v, u, w);
	}

	rep (i, 1, n) if (!dfn[i]) tarjan(i, 0);
	rep (i, 1, n) if (!dcc[i]) ++dcccnt, dfs(i);

	rebuild(); fix(1, 0);

	cin >> q;

	rep (i, 1, q)
	{
		int u, v; cin >> u >> v;
		qry[i] = { dcc[u], dcc[v] };
		Q.add(dcc[u], dcc[v]);
		Q.add(dcc[v], dcc[u]);
	}

	init(dcccnt); tarjanLCA(1);

	rep (i, 1, q)
	{
		int f = LCA(i);
		int u = qry[i].first, v = qry[i].second;
		if (sum[u] + sum[v] - (sum[f] << 1) + siz[f] > 0)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}