两次bfs求树的直径的正确性
2024-10-11 20:45:21
结论:离树上任意点\(u\)最远的点一定是这颗树直径的一个端点。
证明:
若点\(u\)在树的直径上,设它与直径两个端点\(x,y\)的距离分别为\(S1\)、\(S2\),若距离其最远的点\(v\)不是这两个端点,
则\(dist(u,v) > S1 && dist(u,v) > S2\), 则必有\(S1 + dist(u,v) > S1 + S2 或 S2 + dist(u,v) > S1 + S2\),这与\((x,y)\)是直径的
假设相悖。
else
\(u\)不在树的直径上,则其到直径最近的一点\(mid\)的距离为\(dist(u,mid)\),设直径的两端点分别为\(x,y\)。
若距离\(u\)最远的点不是\(x,y\)之一, 设距离\(u\)最远的点为\(v\),
则路径\(u->v\)会出现如下几种情况:
1.完全经过路径\(u->mid\)
2.完全不经过路径\(u->mid\)
3.不完全经过路径\(u->mid\)
这3种情况都能推出\((x,y)\)不是树的直径的结论。
故结论正确。
最新文章
- 使用PhpDocumentor生成文档
- Redis操作命令总结
- POJ(3468)
- CODEVS3123 a*b problem plus (FFT)
- LiveView 0.8 RC1 could boot evidence files acquired from Win10 64bit
- 纯HTML标签详解
- uva10004 Bicoloring 黑白染色问题,DFS
- Spring 简单入门实例
- RPi 2B SD read-only filesytem
- php之类,对象(二)继承性,static静态的,const常量
- hdu1166 经典线段入门
- 男装电子零售商East Dane即将面世_衣装_YOKA时尚网
- Spark数据本地化-->;如何达到性能调优的目的
- JVM-3.内存
- 让两个数x,y一直保持互质的模版
- localhost和127.0.01 区别
- lumion材质系统室内渲染6.3
- 一款好用的轮播插件swiper,适用于移动端和web
- 危险代码:如何使用Unsafe操作内存中的Java类和对象
- 【BZOJ1821】[JSOI2010]部落划分(二分,并查集)
热门文章
- 安卓 apk 嵌入H5页面只显示部分
- SQLServer查看分区表详细信息
- 汉字转拼音,TinyPinyin、Pinyin4j与JPinyin哪个库更快
- 使用python远程连接数据库
- [原创]Spring-Security-Oauth2.0浏览器端的登录项目分享
- mongodb 更新数据时int32变为double的解决办法
- C# FastReport .NET打印
- asp.net oracle 中文乱码 解决方法
- DevOps 转型到底难不难(转自成哥的世界)
- vue chunk-elementUI.3d5a4739.js 过大,网页打开慢开启gzip压缩