Code:

#include<bits/stdc++.h>
#define ll long long
#define maxn 300001
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
deque<int>Q;
int n,S,edges,k;
int hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn<<1],dis[maxn],fa[maxn],mark[maxn];
void add(int u,int v,int c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
void dfs(int u,int ff)
{
if(dis[u]>dis[k]) k=u;
fa[u]=ff;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff || mark[v]) continue;
dis[v]=dis[u]+val[i],dfs(v,u);
}
}
int answer[maxn];
map<int,int>pre,back;
int main()
{
int i,j,x,y;
// setIO("input");
scanf("%d%d",&n,&S);
for(i=1;i<n;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c), add(b,a,c);
}
dis[1]=0, dfs(1,0);
x=k, k=0,dis[x]=0,dfs(x,0),y=k;
//y->x
for(int i=y;i;i=fa[i]) mark[i]=1,pre[i]=dis[i], back[i]=dis[y]-dis[i];
int ans=inf,s=y;
for(int i=y;i;i=fa[i])
{
dis[k=0]=0;
dis[i]=0, dfs(i,fa[i]),answer[i]=dis[k];
while(!Q.empty()&&pre[Q.front()]-pre[i]>S) Q.pop_front();
while(!Q.empty()&&answer[i]>=answer[Q.back()]) Q.pop_back();
while(pre[s]-pre[i]>S) s=fa[s];
Q.push_back(i);
int a=answer[Q.front()];
int b=pre[i];
int c=back[s];
ans=min(ans,max(max(a,b),c));
}
printf("%d\n",ans);
return 0;
}

  

最新文章

  1. UVA227
  2. Qcon会议之所见所想
  3. Effective Java之避免创建不必要的对象
  4. 简化版可用于多线程的logger
  5. 解决UITableView中Cell重用机制导致内容出错的方法总结
  6. 使用Code::Blocks配置Python编译环境
  7. shell之小括号、中括号、大括号
  8. VS2013以管理员身份使用
  9. .net 生成缩略图
  10. 决策树模型组合之随机森林与GBDT
  11. 简单的OC程序
  12. ORACLE 查询某表中的某个字段的类型,是否为空,是否有默认值等
  13. Educational Codeforces Round 61 (Rated for Div. 2)-C. Painting the Fence 前缀和优化
  14. Python爬虫之二
  15. 利用 Eclipse IDE 的强大功能远程调试 Java 应用程序
  16. LeetCode算法题-Sum of Left Leaves(Java实现)
  17. babel-cli 的使用
  18. js数组去除重复数据
  19. mysql 启动和关闭外键约束
  20. 51nod1331 狭窄的通道

热门文章

  1. 【web前端】面题整理(2)
  2. YARN日志聚合相关参数配置
  3. 为什么存储过程比sql语句效率高?
  4. HttpURLConnection 发送http请求帮助类
  5. POJ 3743 LL’s cake(圆+PSLG)
  6. 快速查看php文档技巧
  7. C++的同名属性(没有虚拟属性)、同名普通函数、同名静态函数(没有虚拟静态函数),是否被覆盖
  8. jquery做一个小的轮播插件---有BUG,后续修改
  9. asp.net table表格表头及列固定实现
  10. SpringMVC_放行静态资源