目录1. 前言2. 详解2.1 定义2.2 求法2.2.1 DFS 求解2.2.2 树形 DP 求解2.3 代码3. 总结
1. 前言
树的直径是树的一个小板块，但是有着重要的应用。
前置知识：树的基础知识。
2. 详解
例题：SP1437 PT07Z - Longest path in a tree
2.1 定义
树的直径：一棵树上最长的路径叫做树的直径。
比如下面这棵树，带有边权 1 的路径就是树的直径。
需要注意的是，这棵树的直径不止一条，但是一般情况下我们只取其中一条叫做这棵树的直径。
2.2 求法
那么怎么求树的直径呢？
这里有两种求法：DFS 与树形 DP。
2.2.1 DFS 求解
该算法的大致步骤如下：
首先随便取一个点，做一遍 DFS，求出这个点能够到达的最远点。
然后从这个点再次 DFS，求出这个点能够到达的最远点。
求出来的两个点之间的路径就是树的直径。
步骤简明易懂，那么这个算法为什么是正确的呢？
下面证明假设边权大于 0。
采用反证法：
假设图中还存在一条比我们求出来的路径更长的路径，那么这条路径就是树的直径。
设我们求出的路径为 \(AB\)，真正的直径为 \(CD\)。
分为两种情况：
直径与我们求出的路径相交或者部分重合。
那么根据上述算法，我们在第一次找到点 \(A\) 的时候必有 \(AE>CE\)。
同理，有 \(AE+EF+FB>AE+EF+FD\)。
考虑将 \(AE>CE\) 带入上述不等式，有 \(AE+EF+FB>CE+EF+FD\)，这与 \(CD\) 是直径不符，所以上述情况不成立。
直径与我们求出的路径不重合。
则 \(CF+FD>CF+EF+EB\)，因此 \(FD>EF+EB\)，则有 \(FD>EB\)。
然而根据我们的算法步骤，\(EB>EF+FD\)，则有 \(EB>FD\)。
出现了矛盾，因此原假设错误。
综上所述，\(AB\) 必须是直径。
那么为什么说这个证明必须有边权大于 0 呢？
这是因为如果边权小于 0，那么上述所有证明的 \(a>b+c\rightarrow a>c\) 就都不一定成立了。
同时这也揭示了 DFS 求树的直径必须有所有边权大于 0。
DFS 的优点：可以记录树的直径都有哪些点，也就是可以完整记录路径。
DFS 的缺点：不能处理有负边权的树。
2.2.2 树形 DP 求解
这个需要有一定树形 DP 基础，当然没有基础也没有问题。
考虑设 \(f1_i,f2_i\) 分别表示第 \(i\) 个节点到叶子节点路径的最大值与次大值。
那么设计状态转移方程：
设当前的点为 \(u\)，当前枚举的儿子节点为 \(v\)，边权为 \(val\)，那么有如下方程：
如果 \(f1_v+val>f1_u\)，那么 \(f2_u\leftarrow f1_u,f1_u\leftarrow f1_v+val\)。
否则，\(f2_u=\max\{f2_u,f1_v+val\}\)。
转移方程还是简明易懂的吧qwq
最后的答案就是 \(\max\{f1_i+f2_i|i \in [1,n]\}\)。
那么这个做法很明显，因为是 DP 思想，可以处理具有负边权的树。
树形 DP 的优点：可以处理具有负边权的树。
树形 DP 的缺点：不能记录路径。
2.3 代码
两种做法的代码如下（Solve_dfs 是 DFS 做法，Solve_DP 是树形 DP 做法）：
/*
========= Plozia =========
Author:Plozia
Problem:SP1437 PT07Z - Longest path in a tree
Date:2021/4/27
Another:树的直径模板题
========= Plozia =========
*/
#include
typedef long long LL;
const int MAXN = 1e4 + 10;
int n, Head[MAXN], cnt_Edge = 1, f[MAXN], ans, root, f1[MAXN], f2[MAXN];
struct node { int Next, to, val; } Edge[MAXN << 1];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){ Head[x], y, z }; Head[x] = cnt_Edge; }
void dfs(int now, int father)
{
if (f[now] > ans) { ans = f[now]; root = now; }
for (int i = Head[now]; i; i = Edge[i].Next)
{
int u = Edge[i].to;
if (u == father) continue ;
f[u] = f[now] + Edge[i].val;
dfs(u, now);
}
}
void Solve_DFS()
{
root = 1;
f[root] = 0; dfs(root, 0); ans = 0;
f[root] = 0; dfs(root, 0);
printf("%d\n", ans);
}
void DP(int now, int father)
{
for (int i = Head[now]; i; i = Edge[i].Next)
{
int u = Edge[i].to;
if (u == father) continue ;
DP(u, now);
if (f1[u] + Edge[i].val > f1[now]) { f2[now] = f1[now]; f1[now] = f1[u] + Edge[i].val; }
else { f2[now] = Max(f2[now], f1[u] + Edge[i].val); }
}
}
void Solve_DP()
{
DP(1, 0);
for (int i = 1; i <= n; ++i) ans = Max(ans, f1[i] + f2[i]);
printf("%d\n", ans);
}
int main()
{
n = read();
for (int i = 1; i < n; ++i)
{
int u = read(), v = read();
add_Edge(u, v, 1); add_Edge(v, u, 1);
}
// Solve_DFS(); return 0;
Solve_DP(); return 0;
}
3. 总结
树的直径：树上最长路径。
求法：
两遍 DFS 求解。
优点：可以记录路径。
缺点：不能处理负边权。
树形 DP 求解。
优点：可以处理负边权。
缺点：不能处理路径。