#include<cstdio>
#include<cstring>
#include<iostream>
#define N 600000
using namespace std;
int cnt,n,s,head[N],next[N*],u[N*],v[N*],q[N],h,t,d[N],f[N],mx,rt1,mx1,from[N],zhan[N],tot,mark[N];
int l,r,ans;
void jia(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=a3;
return;
}
bool pan(int a1)
{
int L=,R=tot;
for(;zhan[]-zhan[L]<=a1;L++);
for(;zhan[R]-zhan[tot]<=a1;R--);
if(zhan[L-]-zhan[R+]>s)
return ;
return ;
}
void dfs(int a1)
{
h=;
t=;
q[t]=a1;
memset(f,,sizeof(f));
f[a1]=;
d[a1]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!f[u[i]])
{
if(mark[u[i]])
d[u[i]]=d[p];
else
d[u[i]]=d[p]+v[i];
q[++t]=u[i];
from[u[i]]=p;
f[u[i]]=;
}
}
return;
}
int main()
{
scanf("%d%d",&n,&s);
for(int i=;i<n;i++)
{
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
jia(a1,a2,a3);
jia(a2,a1,a3);
}
dfs();
mx=;
for(int i=;i<=n;i++)
if(mx<d[i])
{
mx=d[i];
rt1=i;
}
dfs(rt1);
mx=;
for(int i=;i<=n;i++)
if(mx<d[i])
{
mx=d[i];
mx1=i;
}
r=d[mx1];
zhan[++tot]=d[mx1];
mark[mx1]=;
for(;mx1!=rt1;)
{
mx1=from[mx1];
zhan[++tot]=d[mx1];
mark[mx1]=;
}
dfs(rt1);
for(int i=;i<=n;i++)
if(d[i]>l)
l=d[i];
for(;l<=r;)
{
int mid=(l+r)>>;
if(pan(mid))
{
ans=mid;
r=mid-;
}
else
l=mid+;
}
printf("%d\n",ans);
return ;
}

显然最长距离最短,一定是在直径上,我们先DFS两遍找出直径,把直径上的边赋值成0,跑一遍dfs,找一个最大值作为l,二分答案判断。

最新文章

  1. WPF资源字典的使用【转】
  2. TOJ 2776 CD Making
  3. Process Explorer使用图文教程
  4. MyEclipse XFire Web Service
  5. Unity3D 常用插件
  6. VC2010中去掉红绝下划线
  7. 用css3制作旋转加载动画的几种方法
  8. 利用dedecms autoindex让文章列表加上序列号
  9. 触发器创建及Navicat中使用
  10. 转--Android学习笔记-实用代码合集
  11. Gradle用户指南(章9:Groovy快速入门)
  12. iOS第三方语音-讯飞语音
  13. iOS: 学习笔记, 透过Boolean看Swift(译自: https://developer.apple.com/swift/blog/ Aug 5, 2014 Boolean)
  14. linux tesseract 安装及部署tess4j项目的常见问题
  15. yarn安装及node升级
  16. python 中爬虫 content和text的区别
  17. cocoa开发Mac小试笔记
  18. OLED屏幕那些次像素有趣的排列方式
  19. 按时间间隔生成cron表达式
  20. Linux vim命令详解

热门文章

  1. mysql概要(六)连接
  2. Visual Studio 2012 RC 中RC表示什么意思
  3. [转载] C++ STL string的Copy-On-Write技术
  4. JS 字符串编码函数(解决URL特殊字符传递问题):escape()、encodeURI()、encodeURIComponent()区别详解
  5. mysql 查询执行的流程
  6. python仿微软记事本
  7. 使用bufferevent进行libevent服务端和客户端的开发
  8. Android 项目中常用到的第三方组件
  9. C#_加密解密
  10. linux笔记:网络命令ping,traceroute,ifconfig,netstat;挂载和卸载命令mount,umount