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