• 题意

给定一张 $n$ 个点 $m$ 条边的无向连通图，每条边存在边权 $w_i$。

存在 $q$ 组询问，每组询问给定 $s, t, r$，询问图中是否存在一条从 $s$ 到 $t$ 的权值为 $r$ 的路径（可以不是简单路径，即点和边都可以被经过任意多次）。

路径的权值定义为：设路径上依次经过边的边权为 $w_0, w_1, w_2 \cdots w_{k - 1}$，那么该路径的权值为 $\displaystyle (\sum_{i = 0}^{k - 1} w_i \cdot 2^i) \bmod p$。$p$ 给定。

$\mathcal{Data~Range}$：$1 \le n, m, q \le 5 \times 10^4, 1 \le p \le 10^6, p \equiv 1 \pmod{2}$。

---

• 题解

首先考虑如下问题：给定一条路径 $s \to t$，要求计算路径的权值。

这个问题朴素的算法是从 $s$ 开始沿着路径一直走，这样我们不得不时刻维护走过路径的长度，这并不是好的。

由于路径是双向的，我们不妨从 $t$ 开始反着走，这样每走一条边 $w_i$，权值就会由 $x$ 变为 $x \cdot 2 + w_i$，这样我们就不需要维护长度这一维信息了，这是极好的。

---

回到原问题。

我们不妨设一个二维状态 $(u, x)$ 表示走到 $u$ 且当前权值为 $x$，那么询问相当于求解 $(s, 0)$ 是否能够到达 $(t, r)$。

接下来我们深入分析此题的性质。

1. 假设 $(u, x)$ 能够到达 $(v, y)$，那么 $(v, y)$ 也能够到达 $(u, x)$。换言之，状态之间形成的是一个无向图。

证明：

任意找到一条 $u \to v$ 的路径，设路径长度为 $l$，权值为 $w_i$。

若初始状态为 $(u, x)$，那么走一次该路径后到达的状态即为 $(v, x \cdot 2^{l} + w_i)$。

走了 $t$ 次该条路径之后，路径的权值即为 $x \cdot 2^{t\cdot l} + w_i \cdot 2^l\cdot (2^{t} - 1)$。

由于 $p$ 为奇数，那么 $2^{\varphi(p)} \equiv 1 \pmod{p}$。也就是说，当 $t = \varphi(p) \cdot 2$ 时，我们仍然可以走回状态 $(u, x)$。

而 $\varphi(p) \cdot 2 > 1$，也就是说我们可以从状态 $(u, x)$ 走到 $(v, x \cdot 2^{l} + w_i)$，再从 $(v, x \cdot 2^{l} + w_i)$ 走回 $(u, x)$。

得证。

下文用 $\Leftrightarrow$ 表示这种关系。

2. 假设图中存在两条边，边权分别为 $a, b$，那么 $(u, x) \Leftrightarrow (u, x + (a - b) \cdot 3)$。

证明：

首先，若存在两条边，边权为 $a, b$ 并与点 $u$ 相连，那么 $(u, x \cdot 4 + b \cdot 3) \Leftrightarrow (u, x) \Leftrightarrow(u , x \cdot 4 + a \cdot 3)$。

由于 $4$ 存在乘法逆元，所以我们可以考虑换元，即用 $x$ 代替 $x \cdot 4 + b \cdot 3$，那么可得 $(u, x) \Leftrightarrow (u, x + (a - b) \cdot 3)$。

考虑扩展这个性质。

假设存在两条边，边权为 $a, b$ 并与点 $v$ 相连，那么上述性质同样满足。

类似上文，我们考虑找出一条 $u \to v$ 的路径，长度为 $l$， 权值为 $w_i$，那么走 $t$ 次该路径后权值由 $x$ 变为 $x \cdot 2^{t \cdot l} + w_i \cdot (2^{t\cdot l} - 1)$。

我们接着在 $v$ 上走，令权值变为 $x \cdot 2^{t \cdot l} + w \cdot 2^l \cdot (2^{t } - 1) + (a - b) \cdot 3 \cdot 2^t$。那么当 $t = \varphi(p) \cdot 2$ 时，我们便走到了状态 $(u, x + (a - b) \cdot 3)$。

接着扩展，我们假设点 $u$ 与点 $v$ 之间存在一条权值为 $b$ 的边，还分别存在一条权值为 $a, c$ 的边与点 $u, v$ 对应相连。

那么 $(u, x) \Leftrightarrow (u, x + (b - a) \cdot 3 + (c - b) \cdot 3)$，也即 $(u, x + (c - a) \cdot 3)$ 。

我们把两次扩展得出的结论相结合，稍加推导便能得出结论。

得证。

---

接下来，我们设 $\displaystyle g' = \gcd_{a, b~\in~\text{E}} (a - b), g = \gcd(g', p)$，那么由裴蜀定理可以得出：$(u, x) \Leftrightarrow (u, x + g \cdot 3)$，也即当 $x \equiv y \pmod{g \cdot 3}$ 时有 $(u, x) \Leftrightarrow (u, y)$。

结合性质 “$x \equiv y \pmod{p}$ 时有 $(u, x) \Leftrightarrow (u, y)$”，我们可以得出：$x \equiv y\pmod{\gcd(g \cdot 3, p)}$ 时有 $(u, x) \Leftrightarrow (u, y)$。

可以发现，我们完全可以用 $\gcd(g\cdot 3, p)$ 代替 $p$，那么下文的 $p$ 皆代表此。

这里有一个细节问题：$g'$ 要怎么计算？实际上，$g'$ 就等于 $\displaystyle \gcd_{i = 1}^m (w_i - w_1)$，证明可以考虑更相减损法，即 $\gcd(a, b) = \gcd(b, a - b)$。

---

考虑到有 $\forall a, b \in \text{E}, g \mid (a - b)$，那么 $a \equiv b \pmod{g}$。也就是说，每条边的边权都可以表示为 $g \cdot k + z$ 形式。

我们不妨把所有边减去 $z$，然后把所有状态的第二维默认加上 $z$。也即：

$$(u, x)' = (u, x + z) \Leftrightarrow (v, (x + z) \cdot 2 + w_i - z) = (v, x \cdot 2 + w_i + z) = (v, x \cdot 2 + w_i)'$$

可以发现，我们只需要把边权进行处理，然后按照其原本的方式操作，是不会造成任何影响的。

---

现在，每一条边的边权都是 $g$ 的倍数了。也就是说，对于状态 $(u, x)'$，它能到达的状态均可以表示为 $(v, x \cdot 2^p + g \cdot q)'$。

显然有 $q \in \{0, 1, 2\}$。

又由于 $(u, x)' \Leftrightarrow (u, x \cdot 4 + w_i \cdot 3)'\Leftrightarrow (u, x \cdot 4)' = (u, x\cdot 2^2)'$，那么状态就只和 $p$ 的奇偶性有关了，也即 $p \in \{0, 1\}$。

这样，对于每个点而言，本质不同的状态只剩下 $6$ 种，这是十分好的优化。

我们如何维护这些状态的连通性呢？枚举每一条边，把两个端点对应的状态用并查集合并即可。

---

回到问题上来，现在我们需要判断 $(s, z)$ 是否能够到达 $(t, r + z)$。

那么我们需要找到 $p, q$ 满足：

1. $(s, 0)'$ 需要能够到达 $(t, 2^p + g \cdot q)'$。

2. 存在 $k_1, k_2$，满足 $z \cdot 2^{k_1 \cdot 2 + p} + g \cdot (q + k_2 \cdot 3) \equiv r + z \pmod{p}$。

对于第一个条件，我们可以用并查集判断。

对于第二个条件，我们可以将式子转化为 $r + z - g \cdot q \equiv z \cdot 2^{k_1 \cdot 2 + p}\pmod{p}$，然后提前预处理后面一部分即可。

---

代码实现：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>

using namespace std;

namespace IO
{
    int f, c;

    template<typename T> inline void _Read(T &k)
    {
        k = 0, f = 1, c = getchar();
        while(!isdigit(c))
        {
            if(c == '-') f = -1;
            c = getchar();
        }
        while(isdigit(c))
        {
            k = (k << 3) + (k << 1) + c - '0';
            c = getchar();
        }
        return k *= f, void();
    }

    template<typename T> inline void _Write(T k)
    {
        if(k < 0) putchar('-'), k = -k;
        if(k > 9) _Write(k / 10);
        return putchar(k % 10 + '0'), void();
    }

    inline int Read32() { int k; _Read(k); return k; }
    inline void Write32(int k, char ed = '\n') { return _Write(k), putchar(ed), void(); }
}

using IO :: Read32;
using IO :: Write32;

namespace Program
{
    const int MAXN = 2000005;

    int n, m, q, mod, g, z, ed[MAXN][3];
    bool f[2][MAXN];

    inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

    namespace Disjoint_Set
    {
        int fa[MAXN], si[MAXN];

        inline void Init()
        {
            for(register int i = 1; i <= n * 6; i++) fa[i] = i, si[i] = 1;
            return;
        }

        inline int Id(int u, int p, int q) { return (u - 1) * 6 + p * 3 + q + 1; }

        inline int Find(int u) { return fa[u] = (u == fa[u] ? u : Find(fa[u])); }

        inline void Merge(int u, int v)
        {
            int fu = Find(u), fv = Find(v);
            if(fu == fv) return;
            if(si[fu] < si[fv]) swap(fu, fv);
            return fa[fv] = fu, si[fu] += si[fv], void();
        }
    }

    using namespace Disjoint_Set;

    inline bool Check(int s, int t, int r)
    {
        for(register int p = 0; p < 2; p++) for(register int q = 0; q < 3; q++) if(Find(Id(t, 0, 0)) == Find(Id(s, p, q)) && f[p][(r + z + g * (3 - q)) % mod]) return true;
        return false;
    }

    inline int Run()
    {
        n = Read32(), m = Read32(), q = Read32(), g = mod = Read32(); 
        for(register int i = 1; i <= m; i++)
        {
            ed[i][0] = Read32(), ed[i][1] = Read32(), ed[i][2] = Read32();
            g = gcd(g, abs(ed[i][2] - ed[1][2]));
        }
        mod = gcd(g * 3, mod), z = ed[1][2] % g, Init();
        for(register int i = 1; i <= m; i++)
        {
            int u = ed[i][0], v = ed[i][1], w = (ed[i][2] - z) / g; 
            for(register int p = 0; p < 2; p++) for(register int q = 0; q < 3; q++)
            {
                Merge(Id(u, p, q), Id(v, p ^ 1, ((q << 1) + w) % 3));
                Merge(Id(v, p, q), Id(u, p ^ 1, ((q << 1) + w) % 3));
            }
        }
        for(register int i = 0, now = z; i < (mod << 1); i++)
        {
            f[i & 1][now] = true;
            now = (now << 1) % mod;
        }
        while(q--)
        {
            int s = Read32(), t = Read32(), r = Read32();
            if(Check(s, t, r)) puts("YES"); else puts("NO");
        }
        return 0;
    }
}

int main() { return Program :: Run(); }

---

完结撒花！