題目鏈接

很經典，突破口藏的很深，求最小值這里，是問題切入點，想到用二分答案，然后思考怎么寫 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

判定方法：