树的直径
树的直径是指树上最远的两点间的距离，又称为树的最远点对。有两种方法求树的直径，时间复杂度都为 \(O(n)\)：
- 做两次 DFS（或 BFS）
- 树形 DP
两种方法有各自的优点和缺点。
做两次 DFS（或 BFS）方法的优点是能得到完整的路径。因为它用搜索的原理，从起点 \(u\) 出发一步一步求 \(u\) 到其他所有点的距离，能记录路径经过了哪些点。缺点是不能用于有负权边的树。
树形 DP 方法的优点是允许树上有负权边。缺点是只能求直径的长度，无法得到这条直径的完整路径。
例题：PT07Z - Longest path in a tree
做两次 DFS（或 BFS）
当边权没有负值时，计算树的直径可以通过做两次搜索遍历解决，步骤如下：
- 从树上的任意点 \(r\) 出发，求距离它最远的点 \(s\)，则 \(s\) 肯定是直径的两个端点之一。
- 从 \(s\) 出发，求距离 \(s\) 最远的点 \(t\)，则 \(t\) 是直径的另一个端点。
因此 \(s\) 和 \(t\) 就是距离最远的两个点，即树的直径的两个端点。
证明
使用反证法，假设 \(x\) 到 \(y\) 才是真正的直径，而第一次遍历找到的距离 \(r\) 最远的点 \(s\) 不为 \(x\) 或 \(y\)。
这个例子说明，以贪心原理进行路径长度搜索，当树上有负权边时，只能获得局部最优，而无法获得全局最优，这与图论中的 Dijkstra 算法不能用于负权边是同样的道理。
#include <cstdio>
#include <vector>
using namespace std;
const int N = 10005;
vector<int> tree[N];
int dis[N]; // 记录距离
void dfs(int u, int fa) {for (int v : tree[u]) {if (v == fa) continue;dis[v] = dis[u] + 1;dfs(v, u);}
}
int main()
{int n;scanf("%d", &n);for (int i = 1; i < n; i++) {int u, v;scanf("%d%d", &u, &v);tree[u].push_back(v); tree[v].push_back(u);} dfs(1, 0); // 任选一个起点（如1）计算到树上每个节点的距离int s = 0;for (int i = 1; i <= n; i++) if (dis[i] > dis[s]) s = i; // 找最远的点s，s是直径的一个端点dis[s] = 0;dfs(s, 0); // 从s出发，计算以s为起点，到树上每个节点的距离int ans = 0;for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);printf("%d\n", ans);return 0;
}
树形 DP
定义状态 \(dp_u\) 表示以 \(u\) 为根节点的子树上，从 \(u\) 出发能到达的最远路径长度，这个路径的终点是 \(u\) 的一个叶子节点。
状态转移：\(dp_u = \max \{ dp_{v} + edge(u,v) \}, \ v \in son_u\)
整棵树的直径怎么求？设 \(f_u\) 代表经过点 \(u\) 的最长路径长度，显然，在所有的 \(f_u\) 中，最大值就是树的直径长度。
如何计算 \(f_u\) ？实际上在 \(dp_u\) 的计算过程中相当于尝试每一棵子树的贡献，而经过 \(u\) 的最长路径实际上可以用最优的两棵子树合并得到，因此只需在枚举子节点计算 \(dp_u\) 时记录最大值和次大值，最大值加次大值即为 \(f_u\) 的结果。
#include <cstdio>
#include <vector>
using namespace std;
const int N = 10005;
vector<int> tree[N];
int dp[N], ans;
void dfs(int u, int fa) {int max1 = 0, max2 = 0;for (int v : tree[u]) {if (v == fa) continue;dfs(v, u);if (dp[v] + 1 > max1) {max2 = max1;max1 = dp[v] + 1;} else if (dp[v] + 1 > max2) {max2 = dp[v] + 1;}}dp[u] = max1;ans = max(ans, max1 + max2);
}
int main()
{int n;scanf("%d", &n);for (int i = 1; i < n; i++) {int u, v;scanf("%d%d", &u, &v);tree[u].push_back(v); tree[v].push_back(u);}dfs(1, 0);printf("%d\n", ans);return 0;
}
习题：P3174 [HAOI2009] 毛毛虫
解题思路
本题要求的最大“毛毛虫”实际上是在树的直径的基础上多了一些“脚”，可以借用求直径的思路。
定义状态 \(dp_u\) 表示以 \(u\) 为根节点的子树上，\(u\) 到某个叶子节点形成的最大“身体+脚”的个数，则有状态转移：\(dp_u = \max \{ dp_v + 1 \} + feet\)，这里的 \(feet\) 代表“脚”的数量，当 \(u\) 没有子树时，就没有额外的“脚”，有子树时，除了作为主干身体的那一枝以外，其他的子树可以留一个点做“脚”。
类似求直径的方法，此时经过点 \(u\) 的最大“毛毛虫”可以基于计算 \(dp_u\) 过程中最大和次大的两次计算来提供毛毛虫的“身体”，则 \(u\) 的其他邻居节点可以提供“脚”。注意这里计算的“脚”的数量要考虑 \(u\) 的父节点。
参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300005;
vector<int> tree[N];
int dp[N], ans;
void dfs(int u, int fa) {int child = 0;int max1 = 0, max2 = 0;for (int v : tree[u]) {if (v == fa) continue;child++;dfs(v, u);if (dp[v] > max1) {max2 = max1; max1 = dp[v]; } else if (dp[v] > max2) {max2 = dp[v];}}dp[u] = max1 + 1 + max(child - 1, 0);ans = max(ans, max1 + max2 + 1 + max(child - 2, 0) + (fa != 0));
}
int main()
{int n, m; scanf("%d%d", &n, &m);while (m--) {int a, b; scanf("%d%d", &a, &b);tree[a].push_back(b); tree[b].push_back(a); }dfs(1, 0);printf("%d\n", ans);return 0;
}
