一句话题意：在一棵n个结点的树上，有m对点对，若将其中一条边的边权修改成0，求m对点对的最大距离的最小值。
这道题正解是二分+树上差分，可是我一开始并没有想到，而是想了另外一个方法。
预处理每对节点的距离（LCA），同时找出最长链，缩短的边一定在这条链上。此过程为O(nlogn)。
枚举链上每一条边，对于所有点对，可以分成两种了：1）经过这条边的点对；2）不经过的。
判断方法：割掉这条边，判断两点是否连通，仍连通，说明不经过，反之经过。于是一棵树就被拆成了两棵。对于经过的路径（包含最长的），距离都会被缩短，但因为最长的路径存在，所以无需考虑经过的其他路径；而不经过的路径之中取个最大值，将最长路径减去边的权和不经过该边的最大值中再取最大值，枚举所有边的时候再取个最小值就OK了。
在链上一条接着一条判断边时，其中的一棵子树会获得更多的节点，其中可能就包括端点，获得其中一个表示此点对经过该边，获得另一个表示不经过了，因为都在子树中连通。这个过程中判断完所有的边后，所有节点都转至子树中，复杂度为O(n)。
对于判断不经过该边的点对的最大值，维护个线段树，开始时维护第i个点对距离d[i]，在得到一个端点后修改成0，另一个也得到时修改回来。此过程为O(nlogn)。
分析结束。
一开始写错了几个细节，15pts；
后来改成了80pts；
再后来改成了95pts；
被一个答案为0的数据卡到了，改正后，100pts。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 6 using namespace std; 7 8 #define re register int 9 #define LL long long 10 #define rep(i, x, y) for (register int i = x; i <= y; ++i) 11 #define repd(i, x, y) for (register int i = x; i >= y; --i) 12 #define maxx(a, b) a = max(a, b) 13 #define minn(a, b) a = min(a, b) 14 15 inline int read() { 16 int w = 0, f = 1; char c = getchar(); 17 while (!isdigit(c)) f = c == ‘-‘ ? -1 : f, c = getchar(); 18 while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ 48), c = getchar(); 19 return w * f; 20 } 21 22 const int maxn = 3e5 + 5; 23 24 struct Edge { 25 int u, v, w, pre; 26 }; 27 28 struct Gph { 29 int n, m, G[maxn]; 30 Edge edges[maxn << 1]; 31 void init(int n) { 32 this->n = n; 33 m = 0; 34 memset(G, 0, sizeof(G)); 35 } 36 void AddEdge(int u, int v, int w) { 37 edges[++m] = (Edge){u, v, w, G[u]}; 38 G[u] = m; 39 } 40 } ES1, ES2; 41 42 struct LCA { 43 int fa[20][maxn], dis[20][maxn], n, m, dep[maxn]; 44 void dfs(int u, int f) { 45 rep(i, 1, log2(dep[u])) fa[i][u] = fa[i-1][fa[i-1][u]], dis[i][u] = dis[i-1][u] + dis[i-1][fa[i-1][u]]; 46 for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) { 47 Edge &e = ES1.edges[i]; 48 if (e.v == f) continue; 49 fa[0][e.v] = u, dep[e.v] = dep[u] + 1, dis[0][e.v] = e.w; 50 dfs(e.v, u); 51 } 52 } 53 int query(int u, int v) { 54 if (dep[u] < dep[v]) u ^= v ^= u ^= v; 55 re res = 0; 56 if (dep[u] != dep[v]) { 57 re dt = dep[u] - dep[v], t = 0; 58 while (dt) { 59 if (dt & 1) res += dis[t][u], u = fa[t][u]; 60 t++; 61 dt >>= 1; 62 } 63 } 64 if (u == v) return res; 65 repd(i, log2(dep[u]), 0) 66 if (fa[i][u] != fa[i][v]) res += dis[i][u] + dis[i][v], u = fa[i][u], v = fa[i][v]; 67 return res + dis[0][u] + dis[0][v]; 68 } 69 } LCA; 70 71 struct SegTree { 72 int val[maxn << 4]; 73 #define lson (o << 1) 74 #define rson (o << 1 | 1) 75 void pushup(int o) { 76 val[o] = max(val[lson], val[rson]); 77 } 78 void build(int o, int l, int r, int *a) { 79 if (l == r) { val[o] = a[l]; return; } 80 re mid = l + r >> 1; 81 build(lson, l, mid, a); 82 build(rson, mid+1, r, a); 83 pushup(o); 84 } 85 void update(int o, int l, int r, int x, int v) { 86 if (l == r) { val[o] = v; return; } 87 re mid = l + r >> 1; 88 if (x <= mid) update(lson, l, mid, x, v); 89 else update(rson, mid+1, r, x, v); 90 pushup(o); 91 } 92 int query() { 93 return val[1]; 94 } 95 } ST; 96 97 int n, m, l[maxn], r[maxn], dis[maxn], vis[maxn], max_i, fa[maxn], d[maxn], ans; 98 99 void dfs1(int u) { 100 vis[u] = 1; 101 for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) { 102 Edge &e = ES1.edges[i]; 103 if (vis[e.v]) continue; 104 fa[e.v] = u; d[e.v] = e.w; 105 dfs1(e.v); 106 } 107 } 108 109 int starr[maxn << 1], g[maxn], cnt = 0, val[maxn << 1], time0[maxn]; 110 111 void AddPoint(int x, int i) { 112 starr[++cnt] = g[x]; 113 val[cnt] = i; 114 g[x] = cnt; 115 } 116 117 void dfs2(int u) { 118 vis[u] = 0; 119 for (re i = g[u]; i; i = starr[i]) { 120 time0[val[i]]++; 121 if (time0[val[i]] == 1) ST.update(1, 1, n, val[i], 0); 122 else ST.update(1, 1, n, val[i], dis[val[i]]); 123 } 124 for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) { 125 Edge &e = ES1.edges[i]; 126 if (!vis[e.v] || e.v == fa[u]) continue; 127 dfs2(e.v); 128 } 129 } 130 131 int main() { 132 n = read(), m = read(); 133 ES1.init(n); 134 rep(i, 1, n-1) { 135 re u = read(), v = read(), w = read(); 136 ES1.AddEdge(u, v, w); 137 ES1.AddEdge(v, u, w); 138 } 139 LCA.fa[0][1] = 1; 140 LCA.dfs(1, -1); 141 rep(i, 1, m) { 142 l[i] = read(); r[i] = read(); 143 AddPoint(l[i], i); 144 AddPoint(r[i], i); 145 dis[i] = LCA.query(l[i], r[i]); 146 if (dis[i] > dis[max_i]) max_i = i; 147 } 148 ST.build(1, 1, n, dis); 149 dfs1(l[max_i]); 150 ans = dis[max_i]; 151 while (r[max_i] != l[max_i]) { 152 dfs2(r[max_i]); 153 minn(ans, max(ST.query(), dis[max_i] - d[r[max_i]])); 154 r[max_i] = fa[r[max_i]]; 155 } 156 printf("%d", ans); 157 return 0; 158 }
原文：https://www.cnblogs.com/ac-evil/p/9780450.html