于 2026 年 1 月 3 日开始写作。
一、基础内容
1. 树的遍历
可以用 DFS 和 BFS 两种方式。
由于太过基础，相信我应该不会连这个都忘掉，故这里不再赘述。
洛谷 P5908 就是这个的模板。
AC 代码：DFS | BFS
2. 树的直径
这里有一点比较重要：距离树中任一节点最远的节点一定是该树某一直径的某一端点。
由此可以得到一个求直径的方法，称为两遍 DFS 法：
- 从任一节点出发开始 DFS 遍历，找到距离其最远的一个节点 \(u\)；
- 再从 \(u\) 开始 DFS 遍历，再找到距离其最远的一个节点 \(v\)；
- 此时 \(u\) 和 \(v\) 便是该树直径的两个端点，这两个端点之间的路径即为该树的直径。