细说LZJ求树的直径

思路

对于任何一个点，求出其不返回父亲节点的最长链和次长链，相加后求max。

做法

dfs带返回值，返回本树的最长链，dfs遍历子树。 将每棵子树的最长链依次和自己的最长链，次长链比较，得到本树的最长链和次长链。 随即用最长链和次长链的和与ans比较，遍历完整棵树后ans为直径长度。

优点

相较于两次dfs（$O(2n)$）时间复杂度小（$O(n)$）。

缺点

基础做法不能求出两端端点，不添加插件不可求出中心。

代码

#include<iostream>
#include<vector>
#define N 400
using namespace std;
vector<pair<int,int>>a[N];//邻接表 
int ans;//直径长度 
int dfs(int u,int f){
	int fd=0,sd=0;//最长链，次长链
	//first_distance,second_distance 
	for(auto i:a[u]){//遍历每个节点 
		int v=i.first,w=i.second;
		if(v==f){//如果是父亲 
			continue;//跳过 
		}
		int d=dfs(v,u)+w;//子树最长链+到子树的距离 
		if(d>fd){//比较first_distance 
			sd=fd;
			fd=d;
		}
		else{
			if(d>sd){//比较second_distance 
				sd=d;
			}
		}
	}
	ans=max(ans,fd+sd);//相加可以理解成把父亲那条链砍掉后的子树直径
	//全部比较即可得到整棵树的直径 
	return fd;//返回最长链 
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

题意

树的直径：它的一个端点到另一个端点的距离是该最长路（仅非负边权时）。

思路

前置芝士：树上任意一个结点到树的直径的一个端点相比到其他点更长。

人话：从随便一个点入手，离这个点最远的点一定是树的直径的一个端点。

先一个搜索（DFS/BFS）找到直径的一个端点，再从这个端点搜索找另一个端点。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int,int>> a[N];
int mx,mxi;
void dfs(int u,int f,int sum){
	for (int i = 0;i < a[u].size();i++){
		if (a[u][i].first != f){
			if (mx < sum + a[u][i].second){
				mx = sum + a[u][i].second;
				mxi = a[u][i].first;
			}
			dfs(a[u][i].first,u,sum + a[u][i].second);
		}
	}
}
void bfs(int u){
	//          u        f  sum
	queue<pair<int,pair<int,int>>> q;
	q.push({u,{0,0}});
	while (!q.empty()){
		int v = q.front().first,f = q.front().second.first,sum = q.front().second.second;
		// v 其实是 u，是当前结点。
		q.pop();
		for (int i = 0;i < a[v].size();i++){
			if (a[v][i].first != f){
				if (mx < sum + a[v][i].second){
					mx = sum + a[v][i].second;
					mxi = a[v][i].first;
				}
				q.push({a[v][i].first,{v,sum + a[v][i].second}});
			}
		}
	}
}
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i < n;i++){
		int u,v,w;
		cin >> u >> v >> w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dfs(1,0,0);
	mx = 0;
	dfs(mxi,0,0);
	// bfs(1);
	// mx = 0;
	// bfs(mxi);
	cout << mx;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct str{
	int u,w,f; 
};
vector<pair<int,int>>g[305];
int maxn1,maxn2;
int s1;
void bfs1(){
	queue<str>q;
	q.push({1,0,0});
	while(!q.empty()){
		str a=q.front();
		q.pop();
		if(a.w>maxn1){
			maxn1=a.w;
			s1=a.u;
		}
		for(auto i:g[a.u]){
			if(i.first==a.f){
				continue;
			}
			else{
				q.push({i.first,a.w+i.second,a.u});
			}
		}
	}
}
void bfs2(){
	queue<str>q;
	q.push({s1,0,0});
	while(!q.empty()){
		str a=q.front();
		q.pop();
		maxn2=max(maxn2,a.w); 
		for(auto i:g[a.u]){
			if(i.first==a.f){
				continue;
			}
			else{
				q.push({i.first,a.w+i.second,a.u});
			}
		}
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	bfs1();
	bfs2();
	cout<<maxn2;
}