题目的意思就是在直径上找一段距离不超过s的路径，使该路径的偏心距最小。

求出直径之后，显然我们可以用双指针扫描一段合法路径。设u1,u2…ut是直径上的点，d[ui]表示从ui出发能到达的最远距离（除直径），那么该路径的偏心距的表达式就是max（max{d[uk]},dist(u1,ui),dist(uj,ut)），其中i<=k<=j；根据直径的最长性，max{d[uk]}中k的取值可以变为1<=k<=t,因为d[ux](1<=x<=i)一定比dist(u1,ui)要小，这是根据直径的最长性可以推导的，j-t的那部分也同理。所以我们只需要用一个定值记录max{d[uk]}(1<=k<=t)就行了，也就是代码中的maxf。

最后要求最小偏心距，对于每段合法路径的偏心距取min就行了。复杂度O(n)。

1 #include
2 using namespace std;
3 const int N=500005;
4 int to[N<<1],nxt[N<<1],edge[N<<1],head[N],tot; 5 int n,s,t,p,q; 6 int d[N],pre[N],a[N],b[N],f[N],sum[N]; 7 bool v[N]; 8 9 void add(int x,int y,int z){ 10 nxt[++tot]=head[x]; 11 head[x]=tot; 12 to[tot]=y; 13 edge[tot]=z; 14 } 15 16 void dfs1(int u,int f){ 17 if(d[u]>d[p]) p=u;
18 for(int i=head[u];i;i=nxt[i]){
19 int v=to[i];
20 if(v==f) continue;
21 d[v]=d[u]+edge[i];
22 dfs1(v,u);
23 }
24 }
25
26 void dfs2(int u,int f){
27 if(d[u]>d[q]) q=u;
28 for(int i=head[u];i;i=nxt[i]){
29 int v=to[i];
30 if(v==f) continue;
31 d[v]=d[u]+edge[i];
32 pre[v]=i;
33 dfs2(v,u);
34 }
35 }
36
37 void dfs(int x){//求从x向外所能到达的最远距离
38 v[x]=true;
39 for(int i=head[x];i;i=nxt[i]){
40 int y=to[i];
41 if(v[y]) continue;
42 dfs(y);
43 f[x]=max(f[x],f[y]+edge[i]);
44 }
45 }
46
47 int main(){
48 cin>>n>>s;
49 tot=1;
50 for(int i=1;i<n;i++){
51 int x,y,z;
52 scanf("%d%d%d",&x,&y,&z);
53 add(x,y,z);add(y,x,z);
54 }
55 dfs1(1,0);
56 dfs2(p,0);
57 while(q!=p){
58 a[++t]=q;//存直径上的点
59 b[t+1]=edge[pre[q]];//存边权
60 q=to[pre[q]^1];
61 }
62 a[++t]=p;
63 for(int i=1;i<=t;i++) v[a[i]]=true;
64 int maxf=0;
65 for(int i=1;i<=t;i++){
66 dfs(a[i]);
67 maxf=max(maxf,f[a[i]]);
68 sum[i]=sum[i-1]+b[i];
69 }
70 int ans=1<<30;
71 for(int i=1,j=1;i<=t;i++){//双指针扫描
72 while(j<t&&sum[j+1]-sum[i]<=s) j++;
73 ans=min(ans,max(maxf,max(sum[i],sum[t]-sum[j])));
74 }
75 cout<<ans<<endl;
76 }