直接求关键点集的 LCA（找 DFS 序最小 / 最大点的 LCA）记为 X，然后树上倍增求所有关键点到 X 的最大值。

复杂度 $O(mn\log n)$ 直接过了，跑的比一些正解还快。

看起来 https://www.luogu.com.cn/discuss/534708 的 hack 数据没加进去。

#include <cstdio>
#include <algorithm>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline int I()
{
    int q = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        q = q * 10 + c - '0', c = getchar();
    return q * f;
}
void P(int x)
{
    if (x >= 10)
        P(x / 10);
    *O++ = x % 10 + '0';
}
struct S
{
    int u, v, w;
} g[200050];
struct E
{
    int v, w, t;
} e[200050];
int n, m, q, p, c, o[50050], b[50050], d[50050], h[50050], f[50050][20], w[50050][20];
inline bool C(int x, int y) { return b[x] < b[y]; }
inline void A(int u, int v, int w)
{
    e[++c] = {v, w, h[u]};
    h[u] = c;
}
void D(int u)
{
    b[u] = ++p;
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v])
        {
            d[v] = d[f[v][0] = u] + 1;
            w[v][0] = e[i].w;
            for (int j = 1; f[v][j - 1]; ++j)
                f[v][j] = f[f[v][j - 1]][j - 1], w[v][j] = max(w[v][j - 1], w[f[v][j - 1]][j - 1]);
            D(v);
        }
}
inline int L(int x, int y)
{
    if (d[x] < d[y])
        swap(x, y);
    while (d[x] > d[y])
        x = f[x][__lg(d[x] - d[y])];
    if (x == y)
        return x;
    for (int k = __lg(d[x]); k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
inline int Q(int x, int y)
{
    int q = 0;
    while (d[x] > d[y])
        q = max(q, w[x][__lg(d[x] - d[y])]), x = f[x][__lg(d[x] - d[y])];
    return q;
}
inline bool B(S a, S b) { return a.w < b.w; }
int F(int x) { return x == o[x] ? x : o[x] = F(o[x]); }
int main()
{
    n = I();
    m = I();
    q = I();
    for (int i = 1; i <= n; ++i)
        o[i] = i;
    for (int i = 0; i < m; ++i)
        g[i] = {I(), I(), I()};
    sort(g, g + m, B);
    for (int i = 0, c = 0, u, v; i < m; ++i)
        if ((u = F(g[i].u)) != (v = F(g[i].v)))
        {
            o[u] = v;
            A(g[i].u, g[i].v, g[i].w);
            A(g[i].v, g[i].u, g[i].w);
            if (++c == n - 1)
                break;
        }
    D(d[1] = 1);
    for (int i = 0, x, y, p, o, r, X, Y; i < q; ++i)
    {
        x = I();
        y = I();
        p = I();
        o = I();
        r = 0;
        X = Y = x + (o + p - x % p) % p;
        for (int j = x + (o + p - x % p) % p; j <= y; j += p)
        {
            if (b[j] < b[X])
                X = j;
            if (b[j] > b[Y])
                Y = j;
        }
        X = L(X, Y);
        for (int j = x + (o + p - x % p) % p; j <= y; j += p)
            r = max(r, Q(j, X));
        P(r);
        *O++ = '\n';
    }
    fwrite(obuf, O - obuf, 1, stdout);
    return 0;
}