树的直径

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

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

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

树的直径一般有两种求法：「两遍 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\} \] 因为次长链可能为负。