定义

树上任意两节点之间最长的简单路径即为树的直径，一棵树可能有多条直径。

求法

依赖于性质1，从根节点开始跑dfs，找到一个离他最远的点，再从找到的点dfs跑一遍即可

对于每个节点记录向子树能延申的最远距离和次远距离，树形DP+换根。最后取最远距离加次远距离最大的即可。

提示：直径的性质基本上都依赖于边权非负这一先决条件，大部分性质都可以通过反证法来证明。
性质1：直径的两端点都是叶子节点。
性质2：树上任意一点能到达的最远的点一定是直径的一个端点。
性质3：所有直径必交于至少一点，并且几何点都重合（几何点定义为其几何中点。几何中点可能不是点，也可能是在边上）。
性质4：若两条直径有重叠的部分，则于重叠部分同一端点引出的两条直径的非重叠的部分的长度相等。
性质5：对于任一直径上的几何点，其到这条直径两条端点距离的最大值等于其到树中任意点距离的最大值。
性质6：在树上与所有点的最大距离最小的几何点唯一，恰为树的几何中心，其与所有点的距离最大值为树的直径的一半（称作半径）。
性质7：对于一棵树，如果对它的叶子节点新连一条边，则直径的两端点至多改变一个。
性质8：有两棵树，直径分别为 \((u,v)\) 和 \((x,y)\) 若用一条边将两颗树连成一颗，则新树的直径两端点一定是 \(u,v,x,y\) 四个点中的两个点。

您可能感兴趣的其他内容