树的直径

前置知识：[树的相关概念]

树的直径定义为任意两节点之间最长的简单路径。

注意树的直径是一条链，而不是一个数。

树的直径一般有两种求法：「两遍 dfs」 和 树形dp。

前者只适用于正权图，而后者可以用于任意带权图。

具体地，「两遍 dfs」 算法流程如下：

1. 随便找个节点跑一遍 dfs ，找到距离它最远的节点 $x$ 。
2. 以节点 $x$ 为起点再跑一次 dfs ，得到距离 $x$ 最远的节点 $y$ 。
3. 链 $x \leadsto y$ 为原树的直径。

树形dp的方法如下：

1. 钦定节点 $1$ 为根（如果是无根树的话）
2. 设 $d_{1,i},~d_{2,i}$ 分别表示以节点 $i$ 为端点的最长&次长链
3. 随便维护一下，然后求出 $d_{1,1},d_{2,1}$ （方便起见，记 $d_1 = d_{1,1},~d_2 = d_{2,1}$ ）
4. 则最后的答案为 $\max\{d_1,d_1+d_2\}$

对于有负边权的情况dfs是错的，例如

如果不巧从 $1$ 开始跑就会挂。因为答案是 4-3-5 。

对于dp的，最后答案应该是

$$\max\{d_1,d_1+d_2\}$$

因为次长链可能为负。