树的直径（2次DFS法+DP法）

定义

引例

给定由 𝑛 个结点构成的树，树边带权，求树上最长路径的长度。

这条最长路径，被称为树的直径。
树的直径有时也可指代该路径长度。

2次DFS法

基本思路

两次 $DFS$ 法的思路很简单，分为两步 （其实就是两次深搜

1.随便找一个幸运节点 $x$ 做 $DFS$ 找出离该节点最远的节点 $y$
2.以 $y$ 为节点，再做一次 $DFS$ 找出离 $y$ 最远的节点 $z$

此时 $y$ 到 $z$ 就是树的一条直径

正确性后续会给出证明

关于 $BFS$

其实这里用两次 $BFS$ 也是可以的，因为本质上是做两次树的遍历求出最长路

不过似乎 $BFS$ 的代码更加简洁？

正确性证明（反证法）

对于正确性的证明，我们采用反证法

首先假设 $y$ 到 $z$ 不是树的直径，树的真实直径是 $x$ 到 $t$

分类讨论：

1.当 $x$ 在真实直径上

显然，$x$ 到 $y$ 大于 $x$ 到 $t$，那么就有 $s$ 到 $y$ 大于 $s$ 到 $z$ 。与假设不符，$pass$

2.当 $x$ 不在真实直径上

2.1.当 $z$ 到 $y$ 与真实直径有重合

由直径的定义可知，$s$ 到 $t$ 应当是树上最长的路径，但 $z$ 到 $t$ 明显更长，矛盾！

2.2.当 $z$ 到 $y$ 与真实直径没有重合

懒的解释了，自己看罢

$Code$

SP1437

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
const int N = 1e4+10;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;

using namespace std;
vector<int> e[N];
int n;
int dis[N];
void dfs(int pos,int fa){
	for(auto to : e[pos]){
		if(to == fa) continue;
		dis[to] = dis[pos] + 1;
		dfs(to,pos);
	}
}
int work(int node){
	dfs(node,0);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(dis[i] > dis[ans]) ans = i;
	}
	return ans;
}
int main(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u); 
	}
	int s1 = work(1);
	dis[s1] = 0;//这里也可以全部都清空
	int s2 = work(s1);
	cout << dis[s2] << endl;
	return 0;
}

注意：两次 $DFS$ 法不能用来处理带负边权的树

附赠树上DP求树的直径

大臣的旅费

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e4+10;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;

using namespace std;
vector<pair<int ,int> > e[N];
int n;
/*int dis[N];
void dfs(int pos,int fa){
	for(auto to : e[pos]){
		if(to == fa) continue;
		dis[to] = dis[pos] + 1;
		dfs(to,pos);
	}
}
int work(int node){
	dfs(node,0);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(dis[i] > dis[ans]) ans = i;
	}
	return ans;
}*/
int ans = 0;
int dp(int pos,int fa){
	int d1 = 0, d2 = 0;
	for(auto to : e[pos]){
		if(to.first == fa) continue;
		int d = dp(to.first,pos) + to.second;
		if(d > d1) d2 = d1,d1 = d;
		else if(d > d2) d2 = d;
	}
	ans = max(ans, d1 + d2);
	return d1;
}
signed main(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v,w;
		cin >> u >> v >> w;
		e[u].push_back(make_pair(v,w));
		e[v].push_back(make_pair(u,w)); 
	}
	/*int s1 = work(1);
	dis[s1] = 0;
	int s2 = work(s1);
	cout << dis[s2] << endl;*/
	dp(1,0);
	cout << (ans+21) * ans/ 2 << endl;
	return 0;
}

DP法

基本思路

其实DP的时间复杂度和两次 $DFS$ 是一样的，都是 $O(n)$ ，不过DP可以解决带负边权的树
而且DP的常数更小

引入

来思考这样一个问题：

假设节点 $u$ 在树的直径上，那么由节点 $u$ 为链头的链中哪两条会组成树的直径

由于树的直径是树上最长的一条链，所以肯定是选取 $u$ 中最长和次长的两条链

没错这就是我们的思路，枚举每一个节点，求出其中最长和次长的两条链

$Code$

int ans = 0;
int dp(int pos,int fa){
	int d1 = 0, d2 = 0;
	for(auto to : e[pos]){
		if(to.first == fa) continue;
		int d = dp(to.first,pos) + to.second;
		if(d > d1) d2 = d1,d1 = d;
		else if(d > d2) d2 = d;
	}
	ans = max(ans, d1 + d2);
	return d1;
}