思路与算法

用树直径两端的距离求每点到最远叶子的距离d，再计算安全值。重链剖分把u到v拆成按行进方向排列的区间，线段树存区间最大安全值；依次跳过最大值不足阈值的区间，在首个可行区间按相应方向找第一个点。

正确性说明

正权树上最远点可取叶子，且任一点的最远距离等于到直径两端距离的较大者，故安全值正确。树链分段按u到v的顺序覆盖路径且无遗漏；区间最大值不足阈值时其中无答案。首个可行区间内方向优先的线段树下降返回该段最早的合格点，所以也是整条路径最早的合格点。

复杂度

三次树遍历、重链与线段树初始化均O(n)，单查询O(log²n)，总O(n+m log²n)，空间O(n)。

易错点

路径有方向，u到v和v到u答案可能不同，区间方向要分别记录。包括两端和单点路径；不存在返回-1。距离和(d+A)B先用64位再取模；深链用迭代遍历避免栈溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll A, B, C;
    cin >> n >> m >> A >> B >> C;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        --u;
        --v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    auto distances = [&](int source) {
        vector<ll> d(n, -1);
        vector<int> q{source};
        d[source] = 0;
        for (size_t i = 0; i < q.size(); i++)
            for (auto e : adj[q[i]])
                if (d[e.first] < 0) {
                    d[e.first] = d[q[i]] + e.second;
                    q.push_back(e.first);
                }
        return d;
    };
    auto d0 = distances(0);
    int left = max_element(d0.begin(), d0.end()) - d0.begin();
    auto dl = distances(left);
    int right = max_element(dl.begin(), dl.end()) - dl.begin();
    auto dr = distances(right);
    vector<int> value(n);
    for (int i = 0; i < n; i++)
        value[i] = ((max(dl[i], dr[i]) + A) * B) % C;
    vector<int> parent(n, -1), depth(n), size(n, 1), heavy(n, -1), order{0};
    for (size_t i = 0; i < order.size(); i++)
        for (auto e : adj[order[i]])
            if (e.first != parent[order[i]]) {
                parent[e.first] = order[i];
                depth[e.first] = depth[order[i]] + 1;
                order.push_back(e.first);
            }
    for (int i = n - 1; i > 0; i--) {
        int u = order[i], p = parent[u];
        size[p] += size[u];
        if (heavy[p] < 0 || size[u] > size[heavy[p]])
            heavy[p] = u;
    }
    vector<int> head(n), pos(n), at(n);
    vector<pair<int, int>> todo{{0, 0}};
    int timer = 0;
    while (!todo.empty()) {
        auto item = todo.back();
        todo.pop_back();
        for (int u = item.first; u >= 0; u = heavy[u]) {
            head[u] = item.second;
            pos[u] = timer;
            at[timer++] = u;
            for (auto e : adj[u])
                if (parent[e.first] == u && e.first != heavy[u])
                    todo.push_back({e.first, e.first});
        }
    }
    int S = 1;
    while (S < n)
        S *= 2;
    vector<int> tree(2 * S, -1);
    for (int i = 0; i < n; i++)
        tree[S + pos[i]] = value[i];
    for (int i = S - 1; i; i--)
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);
    function<int(int, int, int, int, int, int, bool)> first = [&](int p, int L, int R, int l, int r,
                                                                  int limit, bool reverse) {
        if (r < L || R < l || tree[p] < limit)
            return -1;
        if (L == R)
            return at[L];
        int middle = (L + R) / 2;
        int answer;
        if (reverse) {
            answer = first(p * 2 + 1, middle + 1, R, l, r, limit, reverse);
            if (answer < 0)
                answer = first(p * 2, L, middle, l, r, limit, reverse);
        } else {
            answer = first(p * 2, L, middle, l, r, limit, reverse);
            if (answer < 0)
                answer = first(p * 2 + 1, middle + 1, R, l, r, limit, reverse);
        }
        return answer;
    };
    while (m--) {
        int u, v, limit;
        cin >> u >> v >> limit;
        --u;
        --v;
        vector<array<int, 3>> segments, tail;
        while (head[u] != head[v]) {
            if (depth[head[u]] >= depth[head[v]]) {
                segments.push_back({pos[head[u]], pos[u], 1});
                u = parent[head[u]];
            } else {
                tail.push_back({pos[head[v]], pos[v], 0});
                v = parent[head[v]];
            }
        }
        if (depth[u] >= depth[v])
            segments.push_back({pos[v], pos[u], 1});
        else
            segments.push_back({pos[u], pos[v], 0});
        for (auto it = tail.rbegin(); it != tail.rend(); it++)
            segments.push_back(*it);
        int answer = -1;
        for (auto s : segments) {
            answer = first(1, 0, S - 1, s[0], s[1], limit, s[2]);
            if (answer >= 0)
                break;
        }
        cout << (answer < 0 ? -1 : answer + 1) << '\n';
    }
}