有点神仙的。
题意
给定一张 \(n\) 个点 \(m\) 条边的有向图，有边权，进行 \(q\) 次询问（\(n,m,q\le 2\times 10^5\)，边权为不超过 \(10^9\) 的正整数）。
每次询问给定三个参数 \(v,s,t(0\le s<t\le 10^9)\)，你需要回答是否存在一条起点终点均为 \(v\) 的路径，满足 \(\text{路径长}+s\equiv 0\pmod t\)。
题解
按照经验，这种让你找环的题目一定是让你找到一组基能表示任何其它东西。首先考虑一个结论，你可以在一个环上绕 \(t\) 圈使得这个环等于没绕，同时借此到达任何一个环上节点。那么实际上 \(v\) 所在的强连通分量内部的所有环都能为你所用，而且你不会离开强连通分量。那么相当于在若干张独立的强连通图上，去考虑里面所有可能的环。注意到所有环也都可以绕任意圈，所以你由裴蜀定理，只关心所有环的 \(\gcd\)。
接下来，考虑 DFS 树。考虑将一条边 \((u, v)\) 的权值设为它的权值加上 \(u\) 在正图 DFS 树上的深度加上 \(v\) 在反图 DFS 序上的深度。将一个点的权值设为它在正反图上深度之和。容易得到这些都是合法的环长度。接下来，考虑一个任意环，它可以通过每条边的权值，减掉每个点的权值得到（相当于消去了从根走下来和走上去的路径长度）。那么我们就证明了这是一组基，所有环可以被它们组合而来。接下来运用裴蜀定理即可。
代码
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
constexpr int N = 200005;
int n, m, q;
vector<pair<int, LL>> e[N], re[N];
struct Edge { int u, v; LL w; } ed[N];
int dfn[N], low[N], tot_dfn;
int co[N], tot_co;
vector<int> sk; bool insk[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++tot_dfn;
sk.push_back(u), insk[u] = 1;
for (const auto& ee : e[u])
{
if (!dfn[ee.first])
{
tarjan(ee.first);
MIN(low[u], low[ee.first]);
}
else if (insk[ee.first]) MIN(low[u], low[ee.first]);
}
if (low[u] >= dfn[u])
{
++tot_co;
int t;
do {
t = sk.back();
sk.pop_back();
insk[t] = 0;
co[t] = tot_co;
} while (t != u);
}
}
LL dep1[N], dep2[N];
bool vis1[N], vis2[N];
void dfs(int u, LL d[N], vector<pair<int, LL>> ce[N], bool vis[N])
{
vis[u] = 1;
for (const auto& ee : ce[u])
{
if (co[ee.first] != co[u] || vis[ee.first]) continue;
d[ee.first] = d[u] + ee.second;
dfs(ee.first, d, ce, vis);
}
}
LL g[N];
void modi(LL &x, LL y)
{
if (x == -1) x = y;
x = __gcd(x, y);
}
signed main(void)
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> n >> m;
F(i, 1, m)
{
cin >> ed[i].u >> ed[i].v >> ed[i].w;
e[ed[i].u].push_back({ed[i].v, ed[i].w});
re[ed[i].v].push_back({ed[i].u, ed[i].w});
}
F(i, 1, n) if (!dfn[i]) tarjan(i);
F(i, 1, n)
{
if (vis1[i]) continue;
dep1[i] = 0;
dfs(i, dep1, e, vis1);
dep2[i] = 0;
dfs(i, dep2, re, vis2);
}
memset(g, -1, sizeof (g));
F(i, 1, n) modi(g[co[i]], dep1[i] + dep2[i]);
F(i, 1, m)
{
if (co[ed[i].u] != co[ed[i].v]) continue;
modi(g[co[ed[i].u]], dep1[ed[i].u] + dep2[ed[i].v] + ed[i].w);
}
cin >> q;
F(_, 1, q)
{
int u, s, t; cin >> u >> s >> t;
if (g[co[u]] == -1)
{
cout << "NO\n";
continue;
}
if (s % __gcd(g[co[u]], (LL)t) == 0) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}