题目链接

题目概括与评价

很经典，突破口藏的很深，求最小值这里，是问题切入点，想到用二分答案，然后思考怎么写 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

判定方法：

路径长度 <= mid 的路径不用考虑，考虑路径长度 > mid 的路径。这些所有要考虑的路径，要尽量通过让某条边的边权为0，而全部变成路径长度 <= mid 的路径。
选择边的基本思想是贪心。首先这条边必须满足所有路径长度 > mid 的路径都经过该边，如果这条边不符合这个条件，必然会导致一些路径的长度依然 > mid，在符合这个条件的边里，看有没有 max_val - x <= mid 的边（x 是边权，max_val 是最长路径的长度），有则说明所有路径长度 > mid 的路径减去这条边权后，路径长度都会 <= mid，此时返回 true，否则返回 false（我们用了最贪心的策略，依然是之前路径长度为 max_val 的路径的长度 > mid，说明最长路径长度不可能 <= mid）。