专栏文章

树的直径学习笔记

ttsh_qwq
算法·理论参与者 10已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@mip5rznc
此快照首次捕获于
2025/12/03 06:37
3 个月前
此快照最后确认于
2025/12/03 06:37
3 个月前
查看原文

前言

死亡回放：

定义本身是简单的，引理本身是易懂的，但偏偏这玩意太会有机组合了。 ——@VelvetChords
这个算法往往与其他算法组合在一起出题，包括 DP、并查集、LCA、二分等等。

定义

树的直径是指树上任意两点之间最长的简单路径。一棵树可以拥有多条直径，其长度相等。
以下图为例：
δ(2,6),δ(2,6),δ(2,6)\delta(2,6),\delta(2,6),\delta(2,6) 均为树的直径。
当然，这个图只是一个无权图，但是带权图的处理方法没啥区别，就不举例了。
是不是很简单？但是算法简单 ≠\ne 题目简单（这一点后面会印证的）。

求解

那么，我们要如何求解树的直径呢？
常用的方法有 DFS 和 树状 DP，好像也见过拿 BFS 求的，不过没去做具体了解，我们先讲这两种。

DFS 法

DFS 法的优点在于好写（真的），缺点是无法用于带有负边权的树。

步骤

  1. 从任意节点 rr 出发用 DFS 求出离它最远的节点 ss。
  2. 从 ss 出发求离 ss 最远的节点 tt，则 δ(x,y)\delta(x,y) 为树的直径。
如下图所示：

证明

注：该部分内容参考了 OI Wiki。
采用反证法进行证明，记第一次操作出发点 rr，树真实的直径为 δ(s,t)\delta(s,t) ，假设离 rr 最远的节点 xx 不为 ss 或 tt。
按照 rr 的位置进行分类讨论。
情况 11： rr 在 δ(s,t)\delta(s,t) 上：
假设存在 δ(r,x)>δ(r,t)\delta(r,x) > \delta(r,t)，则 δ(v,x)>δ(v,t)  ⟹  δ(s,x)>δ(s,t)\delta(v,x) > \delta(v,t) \implies \delta(s,x)>\delta(s,t)，与 δ(s,t)\delta(s,t) 为树上任意两点之间最长的简单路径矛盾。
情况 22： rr 不在 δ(s,t)\delta(s,t) 上，且 δ(r,x)\delta(r,x) 与 δ(s,t)\delta(s,t) 存在重合部分：
假设存在 δ(r,x)>δ(r,t)\delta(r,x) > \delta(r,t)，则 δ(u,x)>δ(u,t)  ⟹  δ(s,x)>δ(s,t)\delta(u,x) > \delta(u,t) \implies \delta(s,x)>\delta(s,t)，与 δ(s,t)\delta(s,t) 为树上任意两点之间的最长简单路径矛盾。
情况 33： rr 不在 δ(s,t)\delta(s,t) 上，且 δ(r,x)\delta(r,x) 与 δ(s,t)\delta(s,t) 不存在重合部分：
假设存在 δ(v,x)>δ(u,t)\delta(v,x) > \delta(u,t)，则 δ(u,x)>δ(u,t)  ⟹  δ(s,x)>δ(s,t)\delta(u,x) > \delta(u,t) \implies \delta(s,x)>\delta(s,t)，与 δ(s,t)\delta(s,t) 为树上任意两点之间的最长简单路径矛盾。
综上，三种情况下均会产生矛盾，则在一棵树上，从任意节点 rr 出发进行一次 DFS，到达距离最远的节点一定是书的直径的一个端点。
若边权带有负数，情况 33 无法证明，如下图。

代码

此处给出 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);
	}
}
其中 did_i 表示从 rr 出发到每个节点的距离。

树状 DP 法

树形 DP 法的优点是可以在存在负权边的情况下求解出树的直径。

方法

我们记录当 rr 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度 f1f_1 与和最长路径无公共边的次长路径长度 f2f_2，那么直径长度就是 f1+f2f_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];
}

性质

  • 若树上所有边边权均为正，则树的所有直径中点重合（不一定恰好是某节点，可能是边上的任意一点）。
    • 证明： 使用反证法。设两条中点不重合的直径分别为 δ(s,t)\delta(s,t) 与 δ(s′,t′)\delta(s',t')，中点分别为 xx 与 x′x'。显然，δ(s,x)=δ(x,t)=δ(s′,x′)=δ(x′,t′)\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')。

      有 δ(s,t′)=δ(s,x)+δ(x,x′)+δ(x′,t′)>δ(s,x)+δ(x,t)=δ(s,t)\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)，与 δ(s,t)\delta(s,t) 为树上任意两节点之间最长的简单路径矛盾，故性质得证。
      注：引用自 OI Wiki。
  • 若两条直径有重叠部分，则于重叠部分同一段引出的两条直径的费重叠的部分长度相同。
    • 图解：

      如上图，δ(b,s)=δ(a,s),δ(c,t)=δ(t,d)\delta(b,s)=\delta(a,s),\delta(c,t)=\delta(t,d)。
    • 证明： 设两条直线分别为 δ(a,c)，δ(b,d)\delta(a,c)，\delta(b,d)，重叠部分为 δ(s,t)\delta(s,t)。（ss 与 tt 可能重合，即 s=ts=t）。
      如果 δ(s,t)≠δ(s,b)\delta(s,t) \ne \delta(s,b)，此时若再得到 δ(s,t)≠δ(d,t)\delta(s,t) \ne \delta(d,t)，则取 δ(s,a)\delta(s,a) 和 δ(b,s)\delta(b,s) 中较长的一条（长度设为 d1d_1），δ(s,t)\delta(s,t) 和 δ(d,t)\delta(d,t) 中较长的一条（长度设为 d2d_2）。
      若 d1d_1 和 d2d_2 不在同一条直线上，d1+δ(s,t)+d2>δ(a,c)d_1+\delta(s,t)+d_2>\delta(a,c),矛盾，若 d1d_1 和 d2d_2 在同一条直线上 δ(a,c)>δ(b,d)\delta(a,c) > \delta(b,d)，出现矛盾。

模板

具体代码见上，模板题链接。

例题 1

例题一链接 P4408。
hmm，这道题题面怎么这么长，看了半天才看懂。
题面省流：在一棵树上，找 A,B,CA,B,C 三个点，使得 AB+BCAB+BC 最大，并且 AC>ABAC>AB（这点很重要）。
贪心一下可以得出我们只需先令 ABAB 最大，再从 BB 出发寻找一个最长的 BCBC，但是一定要注意 CC 不能是 AA！！！
所以我们只需先找出树的直径 ABAB，再从 BB 出发跑一次 DFS，最终答案就是 min⁡(di,fi)+k\min(d_i,f_i)+k。其中 did_i 是 AA 至 ii 号点的简单路径长，fif_i 是 BB 至 ii 号点的简单路径长，kk 是 ABAB 长，注意 ii 不能是 AA 或 BB。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int n,m,c,d[200005],f[200005];
int first,last;
vector<pair<int,int>>e[200005];
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<<ma;
	return 0;
}

例题 2

P3629。

思路

这道题挺绕的，出题人吃枣药丸，说白了就是在一颗树里找选 K 条路径，让它们不相交部分的长度最大。
本题突破点在于 1≤K≤21\le K \le 2，所以我们只需要分类讨论一下。

K=1

拿原题里的图举例
我们从节点 11 出发，遍历整棵树，一开始每条边需要遍历 22 次，即巡逻距离为 2×(n−1)2\times (n-1)。
为了使巡逻距离变短，我们可以通过连接两个节点形成一条新的边，那么连什么边才能减少最多距离呢？
修建一条道路后，这棵树里就出现了一个环，我们定义 S(x,y)S(x,y) 的为从 xx 到 yy 的距离，比如上面的图中 S(1,6)=3S(1,6)=3，我们从 xx 走到 yy 后，要再回到 xx，这时如果我们在 xx 和 yy 之间连一条边，就可以减少 (S(x,y)−1)(S(x,y)-1) 的距离，−1-1 是因为要走新加的一条边，不难发现 S(x,y)S(x,y) 的最大值就是树的直径的长度。
所以当 K=1K=1 时我们只需要找出树的直径并将其首尾相连即可得到答案，答案是 (2×n−L−1)(2\times n-L-1)。

K=2

推完 K=1K=1 的情况，我们继续推 K=2K=2 的情况，经过第一次处理，我们的图变成了这样。
其中红色边是加入新的边之后形成的环。
但是我们需要再添加一条边，但是如果这两个点之间的路径与原先形成的环有重复的话，重复的部分就会计算两次，所以我们要令不重叠的部分长度最大。
题目原理就是这样，但是怎么去求第二条边缩减小的代价呢？我们可以将这个环上的边权改为 −1-1，再跑一次求直径，但是因为存在负边权，所以要用树状 DP 求。

代码：

CPP
#include<bits/stdc++.h>
#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<pair<int,int>>e[100005];
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<e[u].size();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<n;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<<fat[i]<<" ";
	dfs4(c,0);
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<e[i].size();j++)
//			cout<<e[i][j].first<<" "<<e[i][j].second<<"\n";
//		cout<<"\n";
//	}
	dfs3(1,0);
	cout<<2*n-an-ans;
	//cout<<endl<<an<<" "<<ans;
	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)
	}
}
  1. dcd_c 未归零。
CPP
dfs(1,0);
//此处应有 d[c]=0;
dfs(c,0);
  1. 遍历取最大值时未判断 ii 是否是直径两端。
CPP
for(int i=1;i<=n;i++)
{
//此处应有 if(i!=first&&i!=last)
    ma=max(ma,min(d[i],f[i])+k);
}

结语

终于写完了……
这个可恶的知识点主打一个算法简单，题目极难，还是要多练习的。
练习题嘛，直接在洛谷搜一下好了（主要是我搜不到一个题单）。
update：补充证明过程。

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...