题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MXN = 3e5 + 5;

struct Edge {
    int dest, weight;
};

vector<Edge> g[MXN];
int n, m, mx1 = 0, mx2 = 0, cnt;
int cf[MXN], ds[MXN], ww[MXN],a[MXN], b[MXN], lca[MXN], dep[MXN], id[MXN], top[MXN], fa[MXN], mxson[MXN], siz[MXN];

void addE(int from, int to, int weight) {
    g[from].push_back({to, weight});
    g[to].push_back({from, weight});
}

void dfs1(int v, int ff, int d) {
    id[++cnt] = v, fa[v] = ff, dep[v] = d, siz[v] = 1;
    int MS = 0, MX = 0;
    for (const Edge& e : g[v]) {
        int to = e.dest;
        if (to != ff) {
            ww[to] = e.weight;
            ds[to] = ds[v] + ww[to];
            dfs1(to, v, d + 1);
            if (MX < siz[to]) MX = siz[to], MS = to;
            siz[v] += siz[to];
        }
    }
    mxson[v] = MS;
}

void dfs2(int v, int tt) {
    top[v] = tt;
    if (!mxson[v]) return;
    dfs2(mxson[v], tt);
    for (const Edge& e : g[v]) {
        if (e.dest != fa[v] && e.dest != mxson[v])
            dfs2(e.dest, e.dest);
    }
}

int f(int a, int b) {
    while (top[a] != top[b]) {
        if (dep[top[a]] > dep[top[b]]) {
            a = fa[top[a]];
        } else {
            b = fa[top[b]];
        }
    }
    return dep[a] < dep[b] ? a : b;
}

bool check(int k) {
    memset(cf, 0, sizeof(cf)), cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (ds[a[i]] + ds[b[i]] - ds[lca[i]] * 2 > k) {
            cf[a[i]]++, cf[b[i]]++, cf[lca[i]] -= 2, cnt++;
        }
    }
    for (int i = n; i >= 1; i--) {
        cf[fa[id[i]]] += cf[id[i]];
        if (ww[id[i]] >= mx2 - k && cf[id[i]] == cnt) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a1, b1, w1;
        cin >> a1 >> b1 >> w1;
        addE(a1, b1, w1);
        mx1 = max(mx1, w1);
    }
    cnt = 0;
    dfs1(1, 0, 1);
    dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        lca[i] = f(a[i], b[i]);
        mx2 = max(ds[a[i]] + ds[b[i]] - ds[lca[i]] * 2, mx2);
    }
    int l = mx2 - mx1, r = mx2 + 1, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;

    return 0;
}