求出最长路径之后，枚举删掉的边，从大到小暴力枚举最长的没有经过被删掉的边的路径，可以被卡到 $O(nq)$ 但是最大点不到 1s。

下面这个应该可以 hack 掉。

#include<bits/stdc++.h>
using namespace std;
const int M = 3e5 + 10;

mt19937 rng(random_device{}());

int main() {
    int n = 50000, m = 300000;
    printf("%d %d\n", n, m);
    printf("1 2 1000\n");
    for (int i = 2; i < n - 3; i++) printf("%d %d 1\n", i, i + 1);
    printf("%d %d 1000\n", n - 3, n - 2);
    printf("2 %d 1\n", n - 1);
    printf("%d %d 1\n", n - 3, n);

    for (int i = 1; i <= 150000; i++) printf("1 %d\n", n - 2);
    for (int i = 1; i <= 150000; i++) printf("%d %d\n", n - 1, n);
    return 0;
}

下面是过了的代码。

#include<bits/stdc++.h>
#define N 300010
using namespace std;
struct edge {
    int to, next, w;
}ed[N << 1];
struct node {
    int x, y, z;
}a[N << 1];
struct tree {
    int l, r, w;
}tr[N << 2];
int tot, head[N];
inline void add(int x, int y, int z) {
    ed[++tot].next = head[x];
    ed[tot].to = y;
    ed[tot].w = z;
    head[x] = tot;
}
inline int read() {
    int p = 0;
    char ch = getchar();
    while (ch < '0' || ch>'9')ch = getchar();
    //while (ch > '0' && ch < '9')p = p * 10 + ch - '0', ch = getchar();
    while (ch >= '0' && ch <= '9')p = p * 10 + ch - '0', ch = getchar();
    return p;
}
int top[N], k[N], dfn[N], idx, rev[N], e[N];
int dep[N], siz[N], son[N], fa[N];
inline void dfs1(int u, int f) {
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    fa[u] = f;
    for (int i = head[u]; i; i = ed[i].next) {
        int v = ed[i].to;
        if (v == f)continue;
        k[v] = ed[i].w;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])son[u] = v;
    }
}
inline void dfs2(int x, int vt) {
    top[x] = vt;
    dfn[x] = ++idx;
    rev[idx] = x;
    if (son[x])dfs2(son[x], vt);
    for (int i = head[x]; i; i = ed[i].next) {
        int v = ed[i].to;
        if (v == fa[x] || v == son[x])continue;
        dfs2(v, v);
    }
}
inline void pushup(int rt) {
    tr[rt].w = tr[rt << 1].w + tr[rt << 1 | 1].w;
}
inline int lca(int x, int y) {
    while (top[x] ^ top[y]) {
        //if (top[dep[x]] < dep[top[y]])swap(x, y);
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])swap(x, y);
    return x;
}
inline void build(int rt, int l, int r) {
    tr[rt].l = l, tr[rt].r = r;
    if (l == r) {
        tr[rt].w = k[rev[l]];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
inline int query(int rt, int l, int r) {
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].w;
    }
    int mid = tr[rt].l + tr[rt].r >> 1;
    int sum = 0;
    if (l <= mid)sum += query(rt << 1, l, r);
    if (r > mid)sum += query(rt << 1 | 1, l, r);
    return sum;
}
inline int lca_query(int x, int y) {
    int sum = 0;
    while (top[x] ^ top[y]) {
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        sum += query(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (x == y)return sum;
    if (dep[x] > dep[y])swap(x, y);
    sum += query(1, dfn[x] + 1, dfn[y]);

    return sum;
}
inline bool cmp(node a, node b) {
    return a.z > b.z;
}
int minn = 1145141919;
int main() {
    double st = clock();
    freopen("data.txt", "r", stdin);
    int n = read(), m = read();
    for (int i = 1, x, y, z; i < n; i = -~i) {
        x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    dfs1(1, 0), dfs2(1, 1);
    std::cerr << 1 << '\n';
    build(1, 1, n);
    for (int i = 1; i <= m; i = -~i) {
        a[i].x = read(), a[i].y = read();
        a[i].z = lca_query(a[i].x, a[i].y);
    }
    sort(a + 1, a + m + 1, cmp);
    minn = a[1].z; // !
    //for (int i = m; i >= m; i = ~- i)
    for (int i = 1; i >= 1; i = ~- i) {
        int x = a[i].x, y = a[i].y;
        int as = lca(x, y);
        while (x != as) {
            e[x] = a[i].z - k[x]; // !
            //for (int j = m - 1; j >= 1; j--)
            for (int j = 2; j <= m; j++) {
                int ax = lca(x, a[j].x), ay = lca(x, a[j].y), aa = lca(a[j].x, a[j].y);
                if (((ax == x && ay == aa) || (ay == x && ax == aa)) && aa != x)continue;
                e[x] = max(a[j].z, a[i].z - k[x]);
                break;
            }

            minn = min(minn, e[x]);
            x = fa[x];
        }
        while (y != as) {
            e[y] = a[i].z - k[y]; // !
            //for (int j = m - 1; j >= 1; j--)
            for (int j = 2; j <= m; j++) {
                //int ax = (y, a[j].x), ay = (y, a[j].y), aa = lca(a[j].x, a[j].y);
                int ax = lca(y, a[j].x), ay = lca(y, a[j].y), aa = lca(a[j].x, a[j].y);
                //if ((ax == x && ay == aa) || (ay == x && ax == aa))continue;
                if (((ax == y && ay == aa) || (ay == y && ax == aa)) && aa != y)continue;
                e[y] = max(a[j].z, a[i].z - k[y]);
                break;
            }
            minn = min(minn, e[y]);
            y = fa[y];
        }
    }
    printf("%d", minn);
    double ed = clock();
    std::cerr << (int)(ed - st) << '\n';
}