求树直径的方法在此转载一下大佬们的分析：
可以随便选择一个点开始进行bfs或者dfs，从而找到离该点最远的那个点（可以证明，离树上任意一点最远的点一定是树的某条直径的两端点之一；树的直径：树上的最长简单路径）。再从找到的点出发，找到据该点的最远点，那么这两点就确定了树的一条直径，两点间距即为所求距离。
无意中看到一道水题，也就是POJ 1383
题目中给出了一个无环的迷宫，求出其中最长的一条路
我们知道无环图本质上可以认为就是树，所以此题完全可以使用树的最长链算法
即：随便从某个节点C开始DFS或BFS找到最远的一个点A，再从点A开始DFS或BFS找到最远的一点B，那么路径A->B必然是树上的最长路径。
这个算法很多人都知道并且当做结论使用，但很少看到有人给出正确性证明
所以本人简要分析后，给出一个简单的文字性证明：
（最好拿出纸笔画个图，有助于理解下面这段抽象的语死早描述）
首先我们知道对于一个图我们可以任取一个起始点C作为根来构造生成树（其实本来就是树，就是指定一个根C）
那么我们接下来可以分两种情况来讨论：
1. 若最长链包含树根（起始点C），那么DFS/BFS一次必然能够找到最长链的一端，再DFS/BFS一次必然找到最长链另一端。这种情况很容易理解。
2. 若最长链不包含树根（起始点C），在这里我们可以先做出【断言1】：从起始点C开始DFS/BFS查找最远节点A，一定会在中途遇到最长链上的点（暂且把首次遇到的最长链上的那个点称作TR）；只要遇到了最长链上的点之后，子问题变为从TR作为根寻找最长链，然后就和上面的情况1相同了。
为什么【断言1】一定成立？首先如果最长链不包含起始点C，则最长链必然完全包含于C手下的某个子树T中（而且这个子树的根就是上面所说的TR）。然后用反证法，假设这个子树T的最深节点B的对于起始点C的深度为h(B)，那么如果说从起始点C一直走到某个尽头A而没有经过TR的话，那么我们可以做出【断言2】：点A的深度h(A)必定小于等于h(B)；与前提“A是距离起始点C最远的节点”矛盾。
所以只要【断言2】成立则上述反证成功。
而说明【断言2】仍然是反证法，如果点A的深度h(A)大于h(B)，那么路径(A->C->TR)的长度至少为h(A)+1且大于h(B)，所以路径(A->C->TR->B)的长度一定比子树T中的最长链更长！与前提“最长链一定完全包含于C手下的子树T中”矛盾。
至此得证。原文出处https://blog.csdn.net/macuilxochitl/article/details/19157579
这里讲POJ-1985
题自己看
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 1e9+7
using namespace std;
const int MAXN = ;
const int MAXM = ;
int n,m;
struct EDGE
{
int v,next,w;
}edge[MAXN];
int head[MAXN],e;
int q[MAXN],vis[MAXN],d[MAXN];
void init()
{
e=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)//链式前向星部分
{
edge[e].v=v;
edge[e].w=w;//权重
edge[e].next=head[u];//下一条边
head[u]=e++;//u为节点边的头节点
}
void bfs(int src)
{
for(int i=;i<=n;i++)vis[i]=,d[i]=INF;
int h=,t=;
queue<int>q;
q.push(src);
vis[src]=;
d[src]=;
while(!q.empty())
{
int u=q.front();
q.pop();
for (int i=head[u];i!=-;i=edge[i].next)
{
int v = edge[i].v;
int w = edge[i].w;
if (d[u]+w<d[v]){
d[v]=d[u]+w;
if (!vis[v])
{
q.push(v);//把它存下来
vis[v]=;
}
}
}
}
}
int main(){
int u,v,w;
char k;
scanf("%d%d",&n,&m);
init();
for(int i=;i<=m;i++)
{
scanf("%d%d%d%*s",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
bfs();
int pos=-,mx=-;
for (int i=;i<=n;i++)//找到距离这个点最大的并记录下距离它最远的点
if (d[i]>mx)
{
mx=d[i];
pos=i;
}
bfs(pos);//从距离它最远的点出发，再次bfs找这样就能找到直径
mx=-;
for (int i=;i<=n;i++)
if (d[i]>mx)mx=d[i];
printf("%d\n",mx);
return ;
}
类似题-牛客小白月赛6-桃花，这题没有边权值，可以给边一个权值1
这样答案就是最长链长度+1
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 1e9+7
using namespace std;
const int MAXN = ;
const int MAXM = ;
int n,m;
struct EDGE
{
int v,next,w;
}edge[MAXN];
int head[MAXN],e;
int q[MAXN],vis[MAXN],d[MAXN];
void init()
{
e=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)//链式前向星部分
{
edge[e].v=v;
edge[e].w=w;//权重
edge[e].next=head[u];//下一条边
head[u]=e++;//u为节点边的头节点
}
void bfs(int src)
{
for(int i=;i<=n;i++)vis[i]=,d[i]=INF;
int h=,t=;
q[t++]=src;
vis[src]=;
d[src]=;
while(h<t)
{
int u=q[h++];
for (int i=head[u];i!=-;i=edge[i].next)
{
int v = edge[i].v;
int w = edge[i].w;
if (d[u]+w<d[v]){
d[v]=d[u]+w;
if (!vis[v])
{
q[t++]=v;//把它存下来
vis[v]=;
}
}
}
}
}
int main(){
int u,v,w;
char k;
scanf("%d",&n);
init();
for(int i=;i<=n-;i++)
{
scanf("%d%d",&u,&v);
add(u,v,);
add(v,u,);
}
bfs();
int pos=-,mx=-;
for (int i=;i<=n;i++)
if (d[i]>mx)
{
mx=d[i];
pos=i;
}
bfs(pos);
mx=-;
for (int i=;i<=n;i++)
if (d[i]>mx)mx=d[i];
printf("%d\n",mx+);
return ;
}