首先求树的直径两次bfs即可，实际上bfs就是最短路，因为树上路径是唯一的，所以用任何一种遍历方法都行（spfa和dijkstra当然也可以）。
可以证明，只要求出任意一条直径就行了，为什么呢？考虑一下，如果我们在直径上选了一段，那么最远偏心距可肯定是到直径两端的最大值，和直径外的点无关，只和直径的长度有关。
于是我们求完了直径。然后在直径上搞一搞：很容易想到，如果当前选了一段长度为a，他还可以延伸为b，且a < b < s，那么b的答案一定比a优。因此我们建立一个双指针L,R，代表当前选取的一段的左右端点，当L一定时，R要尽量远，如果超出了s，L指针就向前挪一个节点。其中dis数组就充当了前缀和数组的作用，然后每一次都尝试用max(dis[L], dis[end] - dis[R])更新答案，时间复杂度为O(n)。
需要注意的是，因为我们存路径都是反向存的，因此上面实际上应该是max(dis[R], dis[end] - dis[L])，而且跳的时候不是L++,R++,而是L = pre[L], R = pre[R].
别忘了还有一种情况：就是直径长度小于s，此时的答案应该是不在直径上的点到直径的最大值，只要对于直径上每一个节点向外dfs找就行，因为每一个节点只会遍历一次，所以时间复杂度还是O(n)。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 5e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, s; 38 vector<int> v[maxn], c[maxn]; 39 40 bool vis[maxn]; 41 int dis[maxn], pre[maxn], w[maxn]; 42 int bfs(int s) 43 { 44 Mem(vis); Mem(pre); Mem(w); Mem(dis); 45 queue<int> q; q.push(s); 46 vis[s] = 1; 47 dis[s] = 0; 48 while(!q.empty()) 49 { 50 int now = q.front(); q.pop(); 51 for(int i = 0; i < (int)v[now].size(); ++i) 52 { 53 if(!vis[v[now][i]]) 54 { 55 vis[v[now][i]] = 1; 56 dis[v[now][i]] = dis[now] + c[now][i]; 57 pre[v[now][i]] = now; 58 w[v[now][i]] = c[now][i]; 59 q.push(v[now][i]); 60 } 61 } 62 } 63 int Max = -1, pos; 64 for(int i = 1; i <= n; ++i) if(dis[i] > Max) Max = dis[i], pos = i; 65 return pos; 66 } 67 68 int ans = INF; 69 70 int dfs(int now, int x) 71 { 72 int ret = -1; 73 for(int i = 0; i < (int)v[now].size(); ++i) 74 { 75 if(!vis[v[now][i]]) 76 { 77 vis[v[now][i]] = 1; 78 ret = max(ret, dfs(v[now][i], x + c[now][i])); 79 } 80 } 81 return max(ret, x); 82 } 83 void solve(int b, int a) 84 { 85 Mem(vis); 86 ans = -1; 87 for(int i = b; i; i = pre[i]) {vis[pre[i]] = vis[i] = 1; ans = max(ans, dfs(i, 0));} 88 write(ans); enter; 89 } 90 91 int main() 92 { 93 n = read(); s = read(); 94 for(int i = 1; i < n; ++i) 95 { 96 int x = read(), y = read(), co = read(); 97 v[x].push_back(y); c[x].push_back(co); 98 v[y].push_back(x); c[y].push_back(co); 99 } 100 int a = bfs(1); 101 int b = bfs(a); 102 if(s >= dis[b]) {solve(b, a); return 0;} 103 int L = b, R = b; 104 for(int i = b; i; i = pre[i]) 105 { 106 while(L != R && dis[L] - dis[R] + w[i] > s) L = pre[L]; 107 if(dis[L] - dis[R] + w[i] > s) L = pre[i]; 108 R = pre[i]; 109 ans = min(ans, max(dis[R], dis[b] - dis[L])); 110 } 111 write(ans); enter; 112 return 0; 113 }