树的直径

之前一个题目求树的直径,我是暴力树形dp的..
但是其实是有个性质的,树的直径一定是含有一个深度最深的点.
反证法:假如我当前树的直径不含深度最深的点,那么我一定存在一条路径从深度最深的点到另外一个点的距离比当前dis更大,因为树上任意两点都是有路径的.而树上路径的距离公式是.那么假设我现在最深的点到其中两个点的距离最大值最小,假如我现在这个点和这两个点都没有重叠部分,必定是大于的.假如有重叠部分且是两个部分的公共重叠部分,也必定大于,假如不止公共部分,那么和另外一个距离减少的同时,另外一个在增大.同时也可以证明,任意一个距离最远的点都可以.
证毕.

lpt的小屋 文章被收录于专栏

我想要一份甜甜的爱情

全部评论

相关推荐

饼子吃到撑:学院本是这样的,找工作拼运气,你技术再好人家筛选学历照样沉入海底,海投就行了
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务