细说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;
}

提供一种基于dijkstra算法的解法

众所周知dijk是用来求各个点到一个定点的最短路算法，那我就想：可不可以用它求出最长路呢？

题目求两点间最长距离，我们可以先找到一个最最边缘的点，它相对每一个别的点都最远（可以证明找到的这个点一定是直径的起讫点，因为起点终点关于直径中点对称），再利用dijk逐步找离这个点最远的距离

注意以下正规dijkstra算法与解题代码的区别：

void dijk(int s){
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		int sz=p[u].size();
		for(int j=0;j<sz;j++){
			int v=p[u][j].v;
			int w=p[u][j].w;
			if(d[u]+w<d[v]){//注意小于号
				d[v]=d[u]+w;
				q.push(make_pair(-d[v],v));//注意是负的
        
			}
		}
	}
}

最终代码如下:

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	int v;
	int w;
};
priority_queue<pair<int,int> > q;//接下来dijkstra的遍历点 
int d[100005]={};//到最远点的距离 
vector<node> p[305];//边的属性 
bool vis[305]={};
bool vst[305]={};//两个visit，无意义 
priority_queue<pair<int,int> > maxd;//大根堆存最远的点 
void dfs(int s,int d){
	maxd.push({d,s});//压入当前点，筛选最远 
	for(int i=0;i<p[s].size();i++){
		int u=p[s][i].v;
		int w=p[s][i].w;
		if(!vst[u]){
			vst[u]=1;
			dfs(u,d+w);//向下遍历标深度 
		}
	}
	return;
}
void dijk(int s){//反向dijkstra 
	memset(d,-1,sizeof(d));//求最大，故定义-1便于判断 
	memset(vis,0,sizeof(vis));
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){//开始遍历 
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		int sz=p[u].size();
		for(int j=0;j<sz;j++){
			int v=p[u][j].v;
			int w=p[u][j].w;
			if(vis[v]) continue;
			if(d[u]+w>d[v]){//注意大于号 
				d[v]=d[u]+w;
				q.push(make_pair(d[v],v));//注意是正的
			}
		}
	}
}
int mx=0;
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		p[u].push_back({v,w});
		p[v].push_back({u,w});
	}
	dfs(1,0);//找最远点 
	dijk(maxd.top().second);//从最远点遍历dijk 
	for(int i=1;i<=n;i++){
		mx=max(mx,d[i]);
	}
	cout<<mx<<"\n";//输出最大 
	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;
}