给定一棵树，可能有很多直径，要求在直径上找出两个节点，它们构成了一条路径，其距离≤S（给定），并且使得偏心距最小，求这个最小偏心距的值。
偏心距的定义：距离这条路径最远的点。（点与路径的距离为：路径上，距离路径外的那个节点最近的点的距离）
首先可以分析得到，在一端确定的基础上，这个路径越长越好。
然后，题目说可能有很多直径，我们发现无论选取哪一条直径，都是不影响结果的。因为直径如果有多条，它们公共部分的长度一定是大于其分叉部分的（否则两个分叉就能组成更大的路径了）。
如果这个核只存在于公共部分，那么最小偏心距最差也不会超过公共部分长度（如果超过，那么最小偏心距路径加上公共部分就变成了更大的路径），但不会小于分叉部分长度。
如果只存在于分叉部分，那么不会小于公共部分长度（直径的另一端点）。
如果跨越这两部分，那根据定义，肯定不小于分叉部分长度，并且也要小于公共部分长度。那么分叉部分不是很影响情况。
所以我们可以只选一条直径做就好。
（一）暴力求解
对于直径中，找两个点p与q，这两个点距离在不超过s情况下，要最远。这样的点对数量和直径上点的数量是一样的。然后给这个备选的核打上标记，再dfs时是不可以经过这些点的，也不可以通过它们访问另外的点了。（因为距离路径上最近的点 的距离，才是点与路径的距离，所以为了保证线性复杂度，我们这么去做。后面有一步我们还要用到这种优化——明显不影响答案的项可以随意增减，为的是降低复杂度。况且！！！如果不这样做答案会很混乱！保存的值虽然大了，但是毫无意义，因为我们对每个点取最大值时就取到了这个不合法距离。这样做，是不会访问到相同点的。（否则就成环了））然后以每个点为起点进行dfs，（不访问的都清为-1）找到这个点对应的距离中的最大值。然后给所有的最大值中取出最小值，即为最小偏心距。复杂度O(n²)。
#include <cstdio> #include <cstring> #include <map> #include <algorithm> #define N 500010 using namespace std; map<int, int>cp; struct adj {int to, val, next;}e[2*N]; int n, S, head[N], cnt = 1, fa[N], son[N], d[N], m = 1; bool ok[N]; inline int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - 48; c = getchar();} return x; } inline void ins(int x, int y, int z) {e[++cnt].to = y; e[cnt].val = z; e[cnt].next = head[x]; head[x] = cnt;} void dfs(int x, int f, bool flag) { if(flag) fa[x] = f; for(int i = head[x]; i; i = e[i].next) { int y = e[i].to, z = e[i].val; if(y != f && ok[y]) { d[y] = d[x] + z; dfs(y, x, flag); } } } int main() { n = read(); S = read(); memset(head, 0, sizeof(head)); for(int i = 1; i < n; ++i) { int x = read(), y = read(), z = read(); ins(x, y, z); ins(y, x, z); } memset(ok, true, sizeof(ok)); d[1] = 0; dfs(1, 1, true); int u = 1; for(int i = 2; i <= n; ++i) if(d[u] < d[i]) u = i; d[u] = 0; dfs(u, u, true); int v = 1; for(int i = 2; i <= n; ++i) if(d[v] < d[i]) v = i; ok[v] = false; int tmpv = v; while(u != tmpv) {son[fa[tmpv]] = tmpv; tmpv = fa[tmpv]; ++m; ok[tmpv] = false;} int cur = v, will = v; for(int i = 1; i <= m; ++i) { while(d[will] - d[cur] > S) { cp[will] = son[cur]; will = fa[will]; } cur = fa[cur]; } while(!cp[u]) { cp[will] = u; will = fa[will]; } cur = v; int ans = 0x7fffffff; for(int i = 1; i <= m; ++i) { int tmp = v; while(tmp != cur) {ok[tmp] = true; tmp = fa[tmp];} tmp = cp[cur]; while(tmp != fa[tmp]) {ok[fa[tmp]] = true; tmp = fa[tmp];} tmp = cur; int temp = 0; do { memset(d, 0xff, sizeof(d)); d[tmp] = 0; dfs(tmp, tmp, false); for(int j = 1; j <= n; ++j) if(d[j] > temp && d[j] != 0) temp = d[j]; if(tmp == cp[cur]) break; tmp = fa[tmp]; } while(true); ans = min(ans, temp?temp:0x7fffffff); tmp = v; while(tmp != cur) {ok[tmp] = false; tmp = fa[tmp];} tmp = cp[cur]; while(tmp != fa[tmp]) {ok[fa[tmp]] = false; tmp = fa[tmp];} cur = fa[cur]; } printf("%d", ans); return 0; }（二）二分法（个人感觉这个很难想到）
二分一个答案，然后我们从两端，分别找到距离刚好比这个答案小于或等于的节点（“刚”的意思就不说明了）。把它们作为p与q就好，因为均小于等于答案，可以保证两端是没问题的。并且这样比较靠近中心，对于答案一定有好处。然后检查p,q距离有没有超过s，pq之间点有没有到别的点距离超过答案的。重点都在代码中了。O（nlogsum），sum为总权值。
#include <cstdio> #include <cstring> #include <algorithm> #define N 500010 using namespace std; struct adj {int to, val, next;}e[N*2]; int n, s, head[N], cnt = 1, fa[N], u, v, d[N], d1[N]; bool ok[N]; inline void ins(int x, int y, int z) {e[++cnt].to = y; e[cnt].val = z; e[cnt].next = head[x]; head[x] = cnt;} inline int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - 48; c = getchar();} return x; } void dfs(int x, int f, bool flag) { if(flag) fa[x] = f; for(int i = head[x]; i; i = e[i].next) { int y = e[i].to, z = e[i].val; if(y != f && ok[y]) { d[y] = d[x] + z; dfs(y, x, flag); } } } inline bool check(int atp) { int p = -1, q = -1, cur = v; memset(ok, true, sizeof(ok)); while(true) { if(d1[v] - d1[cur] <= atp) q = cur; else break; if(cur == fa[cur]) break; cur = fa[cur]; } cur = v; while(true) { if(d1[cur] - d1[u] <= atp) {p = cur; break;} if(cur == fa[cur]) break; cur = fa[cur]; } //************重要的改错 if(p == -1 || q == -1) return false; if(d1[q] < d1[p]) return true; //虽然这样应该是错的，但是说明mid有点大，return true是为了让mid小一点 if(d1[q] - d1[p] > s) return false; if(p == q) return true; //*************改错完毕掌声鼓励 cur = q; while(true) {ok[cur] = false; if(cur == p) break; cur = fa[cur];} memset(d, 0xff, sizeof(d)); cur = fa[q]; while(true) { if(cur == p) break; d[cur] = 0; dfs(cur, cur, false); for(int i = 1; i <= n; ++i) if(d[i] > atp) return false; cur = fa[cur]; } return true; } int main() { n = read(); s = read(); memset(head, 0, sizeof(head)); for(int i = 1; i < n; ++i) { int x = read(), y = read(), z = read(); ins(x, y, z); ins(y, x, z); } memset(ok, true, sizeof(ok)); d[1] = 0; dfs(1, 1, true); u = 1; for(int i = 2; i <= n; ++i) if(d[i] > d[u]) u = i; d[u] = 0; dfs(u, u, true); v = 1; for(int i = 2; i <= n; ++i) if(d[i] > d[v]) v = i; //****************范围不要瞎剪枝，也许会出错。直径边权5，3，5，3，6。如果武断的认为r从直径长度一半开始，就错了。因为如果从每一边开始找到一个小于等于13的，也是可以办到的。恰好卡在同一个点上。 int l = 0, r = d[v], mid; int ans = r; memcpy(d1, d, sizeof(d1)); while(l <= r) { mid = (l + r)/2; if(check(mid)) {r = mid - 1; ans = mid;} else l = mid + 1; } printf("%d", ans); return 0; }（三）正解
设直径上的点为x1，x2，……，xt。我们把t个节点标为已访问，然后dfs，求出dmax[i]，表示从xi出发，不经过直径其他点，能访问到的最远距离。
则以xi,xj为端点的偏心距就是：
max（max{dmax[xk]}（其中k∈[i, j]，表示核中间发出的那些距离），dist(x1, xi)，dist(xj, xt) （这是核的两个端点发出的最远距离，因为，非负权树中，距离一个点最远的一定是端点之一，否则不就有新直径了吗？（这就是为什么我们可以两次dfs）））
网上好多做法，在这个时候用单调队列去维护max{dmax[xk]}，已经线性复杂度了。但我们前面红字写到，不影响答案的项可以随意增减。也就是说，dmax[1]，dmax[2]，……，dmax[i - 1]一定小于dist（x1，xi），否则就又构成了新直径。同理，dmax[j + 1]，……，dmax[t]也一定小于dist（xj，xt）。所以，我们把max{dmax[xk]}的k∈[i, j]替换为k∈[1, t]。说的更明白一点，如果i~j这一段比不过两头我们额外添加的，那也会有两个dist把它干掉。如果i~j这一段才是最大值，那两端只不过是打个酱油。
这样做的好处，就是把单调队列省去，直接变为一个常数了。于是这个问题，我们巧妙的解决了。
感谢lyd。
#include <cstdio> #include <cstring> #include <algorithm> #define N 500010 using namespace std; struct adj {int to, val, next;}e[N*2]; int n, s, head[N], cnt = 1, fa[N], u, v, d[N], m = 0, a[N]; bool ok[N]; inline void ins(int x, int y, int z) {e[++cnt].to = y; e[cnt].val = z; e[cnt].next = head[x]; head[x] = cnt;} inline int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - 48; c = getchar();} return x; } void dfs(int x, int f) { fa[x] = f; for(int i = head[x]; i; i = e[i].next) { int y = e[i].to, z = e[i].val; if(y != f) { d[y] = d[x] + z; dfs(y, x); } } } int max1; void dfs1(int x, int f, int dis) { for(int i = head[x]; i; i = e[i].next) { int y = e[i].to, z = e[i].val; if(y != f && ok[y]) { max1 = max(max1, dis + z); dfs1(y, x, dis + z); } } } int main() { n = read(); s = read(); for(int i = 1; i < n; ++i) { int x = read(), y = read(), z = read(); ins(x, y, z); ins(y, x, z); } memset(ok, true, sizeof(ok)); d[1] = 0; dfs(1, 1); u = 1; for(int i = 2; i <= n; ++i) if(d[i] > d[u]) u = i; d[u] = 0; dfs(u, u); v = 1; for(int i = 2; i <= n; ++i) if(d[i] > d[v]) v = i; int cur = v; while(true) {a[++m] = cur; ok[cur] = false; if(cur == u) break; cur = fa[cur];} int maxm = 0; for(int i = 1; i <= m; ++i) { max1 = 0; dfs1(a[i], a[i], 0); maxm = max(maxm, max1); } int i = 1, j = 1, ans = 0x7fffffff; while(true) { while(d[a[i]] - d[a[j]] <= s && j < m) ++j; if(d[a[i]] - d[a[j]] > s) --j; int ansij = max(maxm, max(d[a[1]] - d[a[i]], d[a[j]] - d[a[m]])); ans = min(ans, ansij); if(i == m) break; ++i; } printf("%d", ans); return 0; }做这么多，其实这仨都能过当年的NOIP（即使第一个方法，没有想到越长越好，也无所谓，O（n³）也富裕）。但是亲测，只有最后一个能过bzoj1999（加强版），第二个被卡了。
纪念bzoj第50题。
