CF1515G Phoenix and Odometers

有点神仙的。

题意

给定一张 \(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;
}