树的直径
1. 简介
树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在O(n) 时间内求解。
2. 思路
2.1 两次 DFS
- 首先将任意一个结点 u 看作是树根，然后进行 DFS 求出最远的结点s；则 s一定是树的直径的其中一个端点。
证明 假设结点 s′ 和 t′ 之间唯一的简单路径为树的直径，(a,b) 表示结点a 和 b之间的唯一的简单路径的长度。若该最远点 s 不是树的直径的一个端点，则对于当前根结点 u 来说：
- 如果 s′ 或 t′二者有一个不与 s在同一个子树（假设为 t′），则由于
\begin{array}{c} (s',t') \leq (s',u)+(u,t') \leq (s,u)+(u,t') = (s,t') \end{array}
与 (s′,t′)为直径而 s不是直径的端点矛盾。
- 如果 s′、t′均与 s 在同一个子树，易知树的直径 (s',t')没有经过树根 u。设该子树根为 u′，则易知u' \ne s'且 u' \ne t'且 u' \ne s，于是(u',s) 一定为子树u′ 中的最大值，即 s为子树 u′ 的最远点，对子树u' 同样进行上述分析，以此类推。
综上可知，s 一定是树的直径的一个端点。 推论：树中任意结点的最远点要么是 s，要么是t（(s,t)为树的直径）。 证明同上，略。
- 然后将 v 看作是树根，再进行一次 DFS 求出最远点 t，则 s 与 t之间的简单路径长度即为树的直径。
2.2 树形 DP
- 定义树的高度为树根到所有结点的简单路径的最大值，次高度为树根到所有结点的简单路径第二大的值（高度 \geq 次高度）。
- 对于树中任意一个结点 v，若v 到其子树 l_i中的最远结点的距离为 L_i，设所有 L_i 中最大的二者为L_{1rt} = h_i + (l_i,v)和 L_{2nd} = h_j + (l_j,v)，对应的 v的子树为 l_i和 l_j（没有子树 = 子树对应的L_i 为零，即没有足够的子树可以看作有 L_i 为零的对应子树），则子树 v 中过结点 v的最长简单路径等于
\begin{array}{c} L_{1rt} + L_{2nd} \end{array}
子树 v 的高度等于
\begin{array}{c} \max\{L_k = h_k + l_k\} \end{array}
其中，k 取遍 v的所有子树，L_{1rt} 和 L_{2nd}即对应子树 v 的高度和次高度。
- 由于树的直径一定是以树中某个结点 v′ 为根的子树中过结点 v′的最长简单路径，因此计算每个树结点 u′的过结点 u′的最长简单路径，同时维护一下最大值即可。
- 计算每个树结点 u′ 的过结点 u′的最长简单路径就是一个树形 dp 问题：以当前结点为根的子树的高度和次高度的解取决于其子树的高度，而需要计算的最长简单路径即为 u′子树的高度和次高度之和。
3. 代码
【注】以下模板均是基于无权树求树的直径，有权树只需在前向星中记录一下边权，然后更新结点高度/深度不是 + 1 而是 + 对应边权即可。
3.1 两次 DFS
#include <bits/stdc++.h>
using namespace std;
#ifndef _DIAMETEROFTREE_
#define _DIAMETEROFTREE_
#define ll int
#define MAXN 10005
// 树的直径
struct DiameterOfTree{
// 前向星存边
ll cnt; // 动态开点
ll head[MAXN]; // 第一条出边
struct Edge{
ll to; // 边的终点
ll next; // 下一条边
}e[MAXN<<1]; // 存取双向边
// 初始化前向星
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
// 添加双向边
void addEdge(ll u, ll v) {
// 存取双向边
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt++;
e[cnt].next = head[v];
e[cnt].to = u;
head[v] = cnt++;
}
// DFS 求深度最大的结点
ll ans; // 最大深度结点
ll vis[MAXN]; // 标记数组
ll depth[MAXN]; // 深度数组
void dfs(ll u) {
vis[u] = 1;
for(ll i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if(!vis[v]) {
depth[v] = depth[u] + 1;
if(depth[v] > depth[ans]) {
ans = v;
}
dfs(v);
}
}
}
// 求解树的直径
ll getDiameter(ll u) {
// 第一遍 DFS
ans = u;
memset(vis, 0, sizeof(vis));
memset(depth, 0, sizeof(depth));
dfs(u);
// 第二边 DFS
memset(vis, 0, sizeof(vis));
memset(depth, 0, sizeof(depth));
dfs(ans);
return depth[ans];
}
};
#endif3.2 树形 dp
#include <bits/stdc++.h>
using namespace std;
#ifndef _DIAMETEROFTREE_
#define _DIAMETEROFTREE_
#define ll int
#define MAXN 10005
// 树的直径
struct DiameterOfTree{
// 前向星存边
ll cnt; // 动态开点
ll head[MAXN]; // 第一条出边
struct Edge{
ll to; // 边的终点
ll next; // 下一条边
}e[MAXN<<1]; // 存取双向边
// 初始化前向星
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
// 添加双向边
void addEdge(ll u, ll v) {
// 存取双向边
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt++;
e[cnt].next = head[v];
e[cnt].to = u;
head[v] = cnt++;
}
// DFS 树形 dp
ll diameter; // 树的直径
ll vis[MAXN]; // 标记数组
ll dfs(ll u) {
vis[u] = 1;
ll h1 = 0, h2 = 0;
for(ll i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if(!vis[v]) {
ll h = dfs(v) + 1;
if(h > h1) {
h2 = h1;
h1 = h;
} else if(h > h2) {
h2 = h;
}
}
}
diameter = max(diameter, h1+h2);
return h1;
}
// 求解树的直径
ll getDiameter(ll u) {
diameter = 0;
memset(vis, 0, sizeof(vis));
dfs(u);
return diameter;
}
};
#endif本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录