最大值最小,可以用二分来求解
首先二分一个mid，然后把所有长度大于mid的路径记下来
对于这些路径，找一条被所有这些路径覆盖的并且边权最大的边，如果没有这样的边就返回false
为什么要被所有路径覆盖呢？
因为如果不是被所有路径覆盖，那么就存在一条路径，该路径长度比mid大而且它不会被减去一条边(要删去被所有路径覆盖的并且边权最大的边)，这样mid就不合法了
如果找到了这样一条边，但是这条边减去之后路径长度仍然大于mid，说明当前mid还是不合法，返回false
然后就是对于找到的被所有路径覆盖的边,我们要在路径起、终点遍历数+1,在lca处遍历数-2(差分)，再从叶节点向上累加更新，这样才会不重复
Code：
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 1e6 + 7; 5 ll read() { 6 ll re = 0, f = 1; 7 char ch = getchar(); 8 while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();} 9 while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();} 10 return re * f; 11 } 12 int n, m, sum; 13 int Tid, dis[N], dep[N], num[N], tmp[N], fa[N][21]; 14 //tmp[i]表示i这个点通往父亲的边,目的是记录这条边被遍历的次数 15 int tot, head[N]; 16 struct edge{ 17 int net, to, val; 18 }e[N * 3]; 19 struct LU{//记录每个路径的信息 20 int u, v, lca, len; 21 }lu[N * 3]; 22 void add(int u, int v, int w) { 23 e[++tot] = {head[u], v, w}; 24 head[u] = tot; 25 } 26 void dfs(int u, int f, int deep) { 27 dep[u] = deep; 28 num[++Tid] = u;//记录下dfs序对应哪个节点 29 fa[u][0] = f; 30 for (int i = 1; i <= 20; i++) {//倍增 31 fa[u][i] = fa[fa[u][i - 1]][i - 1]; 32 } 33 for (int i = head[u]; i; i = e[i].net) { 34 int to = e[i].to; 35 if (to == f) { 36 continue; 37 } 38 dis[to] = dis[u] + e[i].val;//记录每一个节点到根节点的距离 39 dfs(to, u, deep + 1); 40 } 41 } 42 int LCA(int x, int y) {//倍增求LCA 43 if (x == y) { 44 return x; 45 } 46 if (dep[x] < dep[y]) { 47 swap(x, y); 48 } 49 int dd = dep[x] - dep[y]; 50 for (int i = 0; i <= 20; i++) { 51 if (dd >> i & 1) { 52 x = fa[x][i]; 53 } 54 } 55 if (x == y) { 56 return x; 57 } 58 for (int i = 20; i >= 0; i--) { 59 if (fa[x][i] != fa[y][i]) { 60 x = fa[x][i]; 61 y = fa[y][i]; 62 } 63 } 64 return fa[x][0]; 65 } 66 bool ok(int mid) { 67 int cnt = 0, rest = 0; 68 //cnt记录有多少条路径长度大于mid,rest记录该条路径与mid的差值 69 memset(tmp, 0, sizeof tmp); 70 for (int i = 1; i <= m; i++) { 71 if (lu[i].len > mid) { 72 tmp[lu[i].u]++, tmp[lu[i].v]++; 73 tmp[lu[i].lca] -= 2;//差分 74 rest = max(rest, lu[i].len - mid);//维护一个最大差值 75 cnt++; 76 } 77 } 78 if (!cnt) {//没有比mid再大的边了 79 return true; 80 } 81 for (int i = n; i >= 1; i--) { 82 tmp[fa[num[i]][0]] += tmp[num[i]];//将边的遍历次数累加 83 } 84 for (int i = 2; i <= n; i++) { 85 if (tmp[i] == cnt && dis[i] - dis[fa[i][0]] >= rest) { 86 //如果有一条边被所有长度大于mid的路径覆盖,并且这条边的长度大于最大差值,即删去该边后最优 87 return true; 88 } 89 } 90 return false; 91 } 92 int main () { 93 n = read(), m = read(); 94 for (int i = 1; i < n; i++) { 95 int u = read(), v = read(), w = read(); 96 add(u, v, w), add(v, u, w); 97 sum += w;//求和作为二分边界 98 } 99 dfs(1, 0, 1); 100 for (int i = 1; i <= m; i++) { 101 lu[i].u = read(), lu[i].v = read(); 102 lu[i].lca = LCA(lu[i].u, lu[i].v); 103 lu[i].len = dis[lu[i].u] + dis[lu[i].v] - 2 * dis[lu[i].lca];//记录这条路径的长度 104 } 105 int l = 0, r = sum; 106 while (l < r) { 107 int mid = (l + r) / 2; 108 if (ok(mid)) {//因为要求最大值最小,所以如果成立的话就要向小的值二分 109 r = mid; 110 } else { 111 l = mid + 1; 112 } 113 } 114 printf("%d ", l); 115 return 0; 116 }