1. 树的直径
树上任意两节点之间最长的简单路径即为树的「直径」。
树的直径有两种求法：两次 DFS 和树形 dp。
1.1 两次 DFS
从树的任意一点 \(x\) 出发，找到距离 \(x\) 最远的节点 \(y\)，随后再从 \(y\) 出发，找到离 \(y\) 最远的节点 \(z\)，则 \(y\rightarrow z\) 即为树的一条直径。
证明考虑使用反证法。令 \(d(s,t)\) 表示真实直径，\(x\) 第一次出发到达点 \(y\)（\(y\ne s,t\)），分三类讨论：
- \(x\) 在 \(s\rightarrow t\) 路径上。则 \(d(x,y)>d(x,t)\Rightarrow d(s,y)>d(s,t)\)，与直径定义矛盾。
- \(x\) 不在\(s\rightarrow t\) 路径上，且 \(x\rightarrow y\) 与 \(s\rightarrow t\) 操作有重合路径。不妨设第一个重合的点为 \(z\)。则 \(d(x,y)>d(x,t)\Rightarrow d(z,y)>d(z,t)\Rightarrow d(s,y)>d(s,t)\)，与直径定义矛盾。