P1099 树网的核

无根树,在直径上找到一条长度不超过s的路径,使得最远的点距离这条路径的距离最短;

首先两遍dfs找到直径(第二次找的时候一定要吧father[]清零)

在找到的直径下枚举长度不超过s的链,ans的下界是直径两端点到这条链距离的最小值;

然后将直径上的点都标记,再次求一下别的点到直径的距离。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,s;
int pre[maxn],last[maxn],other[maxn],len[maxn],l; void add(int x,int y,int z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
} int dis[maxn],father[maxn],vis[maxn];
int l1,l2; void dfs(int x)
{
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(v==father[x]||vis[v]) continue;
father[v]=x;
dis[v]=dis[x]+len[p];
dfs(v);
}
} int main()
{
scanf("%d%d",&n,&s);
for(int i=;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
} dis[]=; dfs();
l1=;
for(int i=;i<=n;i++) if(dis[i]>dis[l1]) l1=i;
memset(father,,sizeof(father));
dis[l1]=; dfs(l1); l2=;
for(int i=;i<=n;i++) if(dis[i]>dis[l2]) l2=i; //printf("??%d %d\n",l1,l2); int ans=,j=l2;
for(int i=l2;i;i=father[i])
{
while(father[j]&&dis[i]-dis[father[j]]<=s) j=father[j];
ans=min(ans,max(dis[l2]-dis[i],dis[j]));
}
for(int i=l2;i;i=father[i]) vis[i]=;
for(int i=l2;i;i=father[i])
{
dis[i]=;
dfs(i);
}
for(int i=;i<=n;i++) ans=max(ans,dis[i]);
printf("%d",ans);
return ;
}

最新文章

  1. android subclipse subversive
  2. Ionic环境搭建
  3. 白话学习MVC(八)Action的执行二
  4. oracle11g空表不能导出记录
  5. unity 脚本(自定义组件)的事件触发关系
  6. 【转】Mybatis Generator最完整配置详解
  7. 学习MVC框架之一
  8. My Eclipse 自动提示
  9. CentOS 删除自带的OpenJDK 和 安装SunJDK
  10. Memcached初体验及原理解说
  11. python中循环删除列表中元素时的坑!
  12. MariaDB导入XXX.sql文件
  13. (cvpr2019 ) Better Version of SRMD
  14. Oracle数据库表的一些宏处理
  15. php使用redis的GEO地理信息类型
  16. freeze
  17. Objective-C RunTime 学习笔记 之 AutoReleasPool
  18. ORM表操作
  19. 转:Java对象序列化
  20. Windows10 Virtualization Technology虚拟化技术功能

热门文章

  1. 3.使用 Code First 迁移更新数据库
  2. java之mybatis之缓存
  3. C# DataTable、DataSet、List、相互转换
  4. 2019 4399java面试笔试题 (含面试题解析)
  5. zookerper安装使用教程
  6. QueryDSL-JPA
  7. Java知识回顾 (14)网络编程
  8. jsonpath_rw操作json
  9. Navicat连接腾讯云服务器上的数据库
  10. Vue编程式跳转