题目链接

很经典，突破口藏的很深，求最小值这里，是问题切入点，想到用二分答案，然后思考怎么写 f_check 函数。

二分答案+树上差分。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 300000 + 5;
const LL Maxm = 300000 + 5;
const LL Maxk = 20;struct node {LL to, e;
};
vector<node> tree[Maxn];struct node3 {LL x, y, e, lca;
} path[Maxm];LL father[Maxn][Maxk], depth[Maxn], rDis[Maxn], faW[Maxn], dfn[Maxn], v_diff[Maxn], maxVal = 0, T = 0;void init(LL u, LL fa) {dfn[++T] = u;father[u][0] = fa;depth[u] = depth[fa] + 1;for (LL i = 1; depth[u] > (1 << i); ++i) {father[u][i] = father[father[u][i - 1]][i - 1];}for (auto elem : tree[u]) {if (elem.to == fa)  continue;rDis[elem.to] = rDis[u] + elem.e;faW[elem.to] = elem.e;init(elem.to, u);}return;
}LL LCA(LL u, LL v) {if (depth[u] < depth[v])  swap(u, v);for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v])  u = father[u][i];}if (u == v)  return u;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {u = father[u][i];v = father[v][i];}}return father[u][0];
}bool f_check(LL mid, LL n, LL m) {if (mid >= maxVal)  return true;for (LL i = 0; i <= n; ++i)  v_diff[i] = 0;LL cnt = 0;for (LL i = 1; i <= m; ++i) {if (path[i].e <= mid)  continue;++v_diff[path[i].x];++v_diff[path[i].y];v_diff[path[i].lca] -= 2;++cnt;}for (LL i = T; i >= 1; --i) {v_diff[father[dfn[i]][0]] += v_diff[dfn[i]];}for (LL i = 1; i <= n; ++i) {if (v_diff[i] >= cnt && maxVal - faW[i] <= mid)  return true;}return false;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, a, b, t;cin >> n >> m;for (LL i = 1; i < n; ++i) {cin >> a >> b >> t;tree[a].push_back({b, t});tree[b].push_back({a, t});}init(1, 0);for (LL i = 1; i <= m; ++i) {cin >> path[i].x >> path[i].y;path[i].lca = LCA(path[i].x, path[i].y);path[i].e = rDis[path[i].x] + rDis[path[i].y] - 2 * rDis[path[i].lca];maxVal = max(maxVal, path[i].e);}LL L = 0, mid = 0, R = maxVal;while (L < R) {mid = L + ((R - L) >> 1);if (f_check(mid, n, m) != false)  R = mid;else  L = mid + 1;}cout << L;return 0;
}

每次思考要求什么，确定要求什么后，用算法实现，遇到卡时间或空间，就换个角度思考，或者通过某些算法或数据结构优化暴力。如此逐步求出问题的解。

是树上问题，本质是求所有路径里的最长路径的最小值，可以进行的操作是将某条边的边权设为0。

求最大值的最小值，可用二分答案。

思考怎么写判定函数，

判定目标：最长路径的长度是否可能<= mid

判定方法：