树的直径学习笔记
tsh_qwq
·
2025-06-01 16:30:31
·
算法·理论
前言
死亡回放：
定义本身是简单的，引理本身是易懂的，但偏偏这玩意太会有机组合了。
——@VelvetChords
这个算法往往与其他算法组合在一起出题，包括 DP、并查集、LCA、二分等等。
定义
树的直径是指树上任意两点之间最长的简单路径。一棵树可以拥有多条直径，其长度相等。
以下图为例：
当然，这个图只是一个无权图，但是带权图的处理方法没啥区别，就不举例了。
是不是很简单？**但是**算法简单 $\ne$ 题目简单（这一点后面会印证的）。
## 求解
那么，我们要如何求解树的直径呢？
常用的方法有 **DFS** 和 **树状 DP**，好像也见过拿 **BFS** 求的，不过没去做具体了解，我们先讲这两种。
### DFS 法
DFS 法的优点在于好写（真的），缺点是无法用于**带有负边权**的树。
#### 步骤
1. 从任意节点 $r$ 出发用 DFS 求出离它最远的节点 $s$。
2. 从 $s$ 出发求离 $s$ 最远的节点 $t$，则 $\delta(x,y)$ 为树的直径。
如下图所示：
#### 证明
**注：该部分内容参考了 OI Wiki。**
采用反证法进行证明，记第一次操作出发点 $r$，树真实的直径为 $\delta(s,t)$ ，假设离 $r$ 最远的节点 $x$ 不为 $s$ 或 $t$。
按照 $r$ 的位置进行分类讨论。
---
**情况 $1$：** $r$ 在 $\delta(s,t)$ 上：
假设存在 $\delta(r,x) > \delta(r,t)$，则 $\delta(v,x) > \delta(v,t) \implies \delta(s,x)>\delta(s,t)$，与 $\delta(s,t)$ 为树上任意两点之间最长的简单路径矛盾。
---
**情况 $2$：** $r$ 不在 $\delta(s,t)$ 上，且 $\delta(r,x)$ 与 $\delta(s,t)$ 存在重合部分：
假设存在 $\delta(r,x) > \delta(r,t)$，则 $\delta(u,x) > \delta(u,t) \implies \delta(s,x)>\delta(s,t)$，与 $\delta(s,t)$ 为树上任意两点之间的最长简单路径矛盾。
---
**情况 $3$：** $r$ 不在 $\delta(s,t)$ 上，且 $\delta(r,x)$ 与 $\delta(s,t)$ 不存在重合部分：
假设存在 $\delta(v,x) > \delta(u,t)$，则 $\delta(u,x) > \delta(u,t) \implies \delta(s,x)>\delta(s,t)$，与 $\delta(s,t)$ 为树上任意两点之间的最长简单路径矛盾。
---
综上，三种情况下均会产生矛盾，则在一棵树上，从任意节点 $r$ 出发进行一次 DFS，到达距离最远的节点一定是书的直径的一个端点。
若边权带有负数，**情况 $3$** 无法证明，如下图。
#### 代码
此处给出 DFS 法的核心代码。
```cpp
void dfs(int u,int fa)
{
for(auto x:e[u])
{
int v=x.first,w=x.second;
if(v==fa)continue;
d[v]=d[u]+w;
if(d[v]>d[c])c=v;
dfs(v,u);
}
}
```
其中 $d_i$ 表示从 $r$ 出发到每个节点的距离。
---
### 树状 DP 法
树形 DP 法的优点是可以在**存在负权边的情况**下求解出树的直径。
#### 方法
我们记录当 $r$ 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度 $f_1$ 与**和最长路径无公共边**的次长路径长度 $f_2$，那么直径长度就是 $f_1 + f_2$ 的最大值。
#### 代码
```cpp
void dfs(int u,int fa)
{
f1[u]=f2[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=e[i];
if(v==fa)continue;
dfs(v,u);
int t=f1[v]+w[i];
if(t>f1[u])
{
f2[u]=f1[u];
f1[u]=t;
}
else if(t>f2[u])
{
f2[u]=t;
}
}
f[u]=f1[u]+f2[u];
if(f[u]>ans)ans=f[u];
}
```
## 性质
- 若树上所有边边权均为正，则树的所有直径中点重合（不一定恰好是某节点，可能是边上的任意一点）。
- **证明：** 使用反证法。设两条中点不重合的直径分别为 $\delta(s,t)$ 与 $\delta(s',t')$，中点分别为 $x$ 与 $x'$。显然，$\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')$。
有 $\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)$，与 $\delta(s,t)$ 为树上任意两节点之间最长的简单路径矛盾，故性质得证。
**注：引用自 [OI Wiki](https://oi-wiki.org/graph/tree-diameter/#%E6%80%A7%E8%B4%A8)。**
- 若两条直径有重叠部分，则于重叠部分同一段引出的两条直径的费重叠的部分长度相同。
- **图解：**
如上图，$\delta(b,s)=\delta(a,s),\delta(c,t)=\delta(t,d)$。
- **证明：** 设两条直线分别为 $\delta(a,c)，\delta(b,d)$，重叠部分为 $\delta(s,t)$。（$s$ 与 $t$ 可能重合，即 $s=t$）。
如果 $\delta(s,t) \ne \delta(s,b)$，此时若再得到 $\delta(s,t) \ne \delta(d,t)$，则取 $\delta(s,a)$ 和 $\delta(b,s)$ 中较长的一条（长度设为 $d_1$），$\delta(s,t)$ 和 $\delta(d,t)$ 中较长的一条（长度设为 $d_2$）。
若 $d_1$ 和 $d_2$ 不在同一条直线上，$d_1+\delta(s,t)+d_2>\delta(a,c)$,矛盾，若 $d_1$ 和 $d_2$ 在同一条直线上 $\delta(a,c) > \delta(b,d)$，出现矛盾。
## 模板
具体代码见上，[模板题链接](https://www.luogu.com.cn/problem/B4016)。
## 例题 1
例题一链接 [P4408](https://www.luogu.com.cn/problem/P4408)。
hmm，这道题题面怎么这么长，看了半天才看懂。
题面省流：在一棵树上，找 $A,B,C$ 三个点，使得 $AB+BC$ 最大，并且 $AC>AB$（这点很重要）。
贪心一下可以得出我们只需先令 $AB$ 最大，再从 $B$ 出发寻找一个最长的 $BC$，但是一定要注意 $C$ 不能是 $A$！！！
所以我们只需先找出树的直径 $AB$，再从 $B$ 出发跑一次 DFS，最终答案就是 $\min(d_i,f_i)+k$。其中 $d_i$ 是 $A$ 至 $i$ 号点的简单路径长，$f_i$ 是 $B$ 至 $i$ 号点的简单路径长，$k$ 是 $AB$ 长，注意 $i$ 不能是 $A$ 或 $B$。
代码：
```cpp
#include
#define int long long
#define endl "\n"
using namespace std;
int n,m,c,d[200005],f[200005];
int first,last;
vector
void dfs(int u,int fa)
{
for(auto x:e[u])
{
int v=x.first,w=x.second;
if(v==fa)continue;
d[v]=d[u]+w;
if(d[v]>d[c])c=v;
dfs(v,u);
}
}
void dfs2(int u,int fa)
{
for(auto x:e[u])
{
int v=x.first,w=x.second;
if(v==fa)continue;
f[v]=f[u]+w;
if(f[v]>f[c])c=v;
dfs2(v,u);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(1,0);
d[c]=0;
first=c;
dfs(first,0);
int k=d[c];
last=c;
dfs2(last,0);
int ma=0;
for(int i=1;i<=n;i++)
if(i!=first&&i!=last)
ma=max(ma,min(d[i],f[i])+k);
cout< return 0; } ``` ## 例题 2 [P3629](https://www.luogu.com.cn/problem/P3629)。 ### 思路 这道题挺绕的，~~出题人吃枣药丸~~，说白了就是**在一颗树里找选 K 条路径，让它们不相交部分的长度最大**。 本题突破点在于 $1\le K \le 2$，所以我们只需要分类讨论一下。 #### K=1 拿原题里的图举例  我们从节点 $1$ 出发，遍历整棵树，一开始每条边需要遍历 $2$ 次，即巡逻距离为 $2\times (n-1)$。 为了使巡逻距离变短，我们可以通过连接两个节点形成一条新的边，那么连什么边才能减少最多距离呢？ 修建一条道路后，这棵树里就出现了一个环，我们定义 $S(x,y)$ 的为从 $x$ 到 $y$ 的距离，比如上面的图中 $S(1,6)=3$，我们从 $x$ 走到 $y$ 后，要再回到 $x$，这时如果我们在 $x$ 和 $y$ 之间连一条边，就可以减少 $(S(x,y)-1)$ 的距离，$-1$ 是因为要走新加的一条边，不难发现 $S(x,y)$ 的最大值就是**树的直径**的长度。 所以当 $K=1$ 时我们只需要找出树的直径并将其**首尾相连**即可得到答案，答案是 $(2\times n-L-1)$。 #### K=2 推完 $K=1$ 的情况，我们继续推 $K=2$ 的情况，经过第一次处理，我们的图变成了这样。  其中红色边是加入新的边之后形成的环。 但是我们需要再添加一条边，但是如果这两个点之间的路径与原先形成的环有重复的话，重复的部分就会计算两次，所以我们要令**不重叠的部分**长度最大。 题目原理就是这样，但是怎么去求第二条边缩减小的代价呢？我们可以将这个环上的边权改为 $-1$，再跑一次求直径，但是因为存在负边权，所以要用**树状 DP** 求。 ### 代码： ```cpp #include #define int long long #define endl "\n" using namespace std; int n,k,c,d[100005],fat[100005],fath[100005]; int f[100005],f1[100005],f2[100005]; int head,tail; int ans; vector void dfs(int u,int fa) { for(auto x:e[u]) { int v=x.first,w=x.second; if(v==fa)continue; d[v]=d[u]+w; if(d[v]>d[c])c=v; dfs(v,u); } } void dfs2(int u,int fa) { for(auto x:e[u]) { int v=x.first,w=x.second; if(v==fa)continue; fat[v]=u; d[v]=d[u]+w; if(d[v]>d[c])c=v; dfs2(v,u); } } void dfs3(int u,int fa) { f1[u]=f2[u]=0; for(auto i:e[u]) { int v=i.first,w=i.second; if(v==fa)continue; dfs3(v,u); int t=f1[v]+w; if(t>f1[u]) { f2[u]=f1[u]; f1[u]=t; } else if(t>f2[u]) { f2[u]=t; } } f[u]=f1[u]+f2[u]; ans=max(ans,f[u]); } void dfs4(int u,int fa) { for(int i=0;i { int v=e[u][i].first; if(v==fa||v!=fat[u])continue; fath[v]=u; c=v; e[u][i].second=-1; dfs4(v,u); } } signed main() { // ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); cin>>n>>k; for(int i=1;i { int u,v; cin>>u>>v; e[u].push_back({v,1}); e[v].push_back({u,1}); } dfs(1,0); d[c]=0; dfs2(c,0); if(k==1) { cout<<2*n-d[c]-1; return 0; } int an=d[c]; dfs4(c,0); for(int i=1;i<=n;i++)fat[i]=fath[i]; //for(int i=1;i<=n;i++)cout< dfs4(c,0); // for(int i=1;i<=n;i++){ // for(int j=0;j // cout< // cout<<"\n"; // } dfs3(1,0); cout<<2*n-an-ans; //cout< return 0; } ``` ## 常见错误 1. 函数套用错误。 ```cpp void dfs2(int u,int fa) { for(auto x:e[u]) { int v=x.first,w=x.second; if(v==fa)continue; fat[v]=u; d[v]=d[u]+w; if(d[v]>d[c])c=v; dfs1(v,u);//应为 dfs2(v,u) } } ``` 2. $d_c$ 未归零。 ```cpp dfs(1,0); //此处应有 d[c]=0; dfs(c,0); ``` 3. 遍历取最大值时未判断 $i$ 是否是直径两端。 ```cpp for(int i=1;i<=n;i++) { //此处应有 if(i!=first&&i!=last) ma=max(ma,min(d[i],f[i])+k); } ``` ## 结语 终于写完了…… 这个可恶的知识点主打一个算法简单，题目极难，还是要多练习的。 练习题嘛，直接在[洛谷搜一下好了](https://www.luogu.com.cn/problem/list?tag=213)（主要是我搜不到一个题单）。 update：补充证明过程。