题目传送门

Description

Solution

看起来是一道很棘手的题目(其实真的很毒瘤)

首先处理最长链,我直接找出直径,每个点到直径两端点距离的最大值就是最长链的长度。

询问怎么办?

假如从每个点BFS,复杂度接近 $O(n^2)$ ,然而我们预处理距离只用了 $O(n)$ 的时间,时间复杂度分配不合理。

我们要想办法均摊复杂度。这其实是一种非常有用的解题思路。

我们想到了倍增LCA。

仔细思考,对于两个点 $x,y$ ,目标点需要离 $x$ 尽可能地近,也就是说要离 $y$ 尽可能地远。

所以我们只需要处理LCA的两条链就可以了。

如何判断是否出现了目标点?在倍增预处理的时候,维护一段的最大值就可以辣!

再附一张图

Code

/*
 * @Name: 110757
 * @Author: Lovely_XianShen
 * @Date: 2019-11-02 09:21:13
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

int n, m, p[N][30], cnt, head[N], g[N][39], aqours[N], dep[N];
int dis1[N], dis2[N], s[N];

struct edge {
    int to, nxt, v;
} e[N << 1];

inline void add(int x, int y, int z) {
    e[++cnt].to = y;
    e[cnt].v = z;
    e[cnt].nxt = head[x];
    head[x] = cnt;
}

void dfs(int x, int fa, int dis[], int depth) {
    dis[x] = depth;
    for (int i = head[x]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa)
            continue;
        dfs(to, x, dis, depth + e[i].v);
    }
}

void dfs1(int x, int fa, int depth) {
    p[x][0] = fa;
    g[x][0] = s[fa];
    dep[x] = depth;
    for (int i = head[x]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa)
            continue;
        dfs1(to, x, depth + 1);
    }
}

inline int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    if (x == y)
        return x;
    for (int i = aqours[dep[x]]; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = p[x][i];
    if (x == y)
        return x;
    for (int i = aqours[dep[x]]; i >= 0; i--)
        if (p[x][i] && p[y][i] && p[x][i] != p[y][i])
            x = p[x][i], y = p[y][i];
    return p[x][0];
}

inline int Askx(int x, int k, int q) {
    if (!k)
        return g[x][k] >= q ? p[x][0] : -1;
    if (g[x][k] >= q) {
        int tmp = Askx(x, k - 1, q);
        return tmp != -1 ? tmp : Askx(p[x][k - 1], k - 1, q);
    }
    return -1;
}
inline int Asky(int x, int k, int q) {
    if (!k)
        return g[x][k] >= q ? p[x][0] : -1;
    if (g[x][k] >= q) {
        int tmp = Asky(p[x][k - 1], k - 1, q);
        return tmp != -1 ? tmp : Asky(x, k - 1, q);
    }
    return -1;
}

signed main() {
    n = read();
    m = read();
    int A = read(), B = read(), C = read();
    for (int i = 2; i <= n; i++)
        aqours[i] = aqours[i >> 1] + 1;
    int x, y, z;
    for (int i = 1; i < n; i++) {
        x = read();
        y = read();
        z = read();
        add(x, y, z);
        add(y, x, z);
    }
    int st, ed, maxn = -0x3f3f3f3f;
    dfs(1, 0, dis1, 0);
    for (int i = 1; i <= n; i++)
        if (maxn < dis1[i])
            maxn = dis1[i], st = i;
    dfs(st, 0, dis1, 0);
    maxn = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        if (maxn < dis1[i])
            maxn = dis1[i], ed = i;
    dfs(ed, 0, dis2, 0);
    for (int i = 1; i <= n; i++)
        dis1[i] = max(dis1[i], dis2[i]), s[i] = (dis1[i] + A) * B % C;
    dfs1(1, 0, 1);
    for (int j = 1; j <= aqours[n]; j++)
        for (int i = 1; i <= n; i++)
            if (p[i][j - 1]) {
                p[i][j] = p[p[i][j - 1]][j - 1];
                g[i][j] = max(g[i][j - 1], g[p[i][j - 1]][j - 1]);
            }
    while (m--) {
        int x = read();
        int y = read();
        int z = read();
        if (s[x] >= z) {
            printf("%lld\n", x);
            continue;
        }
        int u = lca(x, y), ans = -1, tmpy = y;
        for (int i = aqours[dep[x]]; i >= 0; i--)
            if (dep[x] - (1 << i) >= dep[u]) {
                ans = Askx(x, i, z);
                if (ans != -1) {
                    printf("%lld\n", ans);
                    break;
                }
                x = p[x][i];
            }
        if (ans != -1)
            continue;
        for (int i = aqours[dep[y]]; i >= 0; i--)
            if (dep[y] - (1 << i) >= dep[u]) {
                int r = Asky(y, i, z);
                if (ans == -1 || (r != -1 && dep[r] < dep[ans]))
                    ans = r;
                y = p[y][i];
            }
        if (ans == -1)printf("%lld\n", s[tmpy] >= z ? tmpy : -1);
        else printf("%lld\n", ans);
    }
    return 0;
}