树的直径
Summary
树的直径指树上最长的一条简单路径。两次 DFS 求解：先从任意点出发找到距离最远的点 u，再以 u 为起点找到距离它最远的点 v，路径 u 到 v 即为直径。做法依据一个结论——从任意点能到达的最远点必是某条直径的端点。实现上用 dfs 维护每个点的深度并记录当前最深点，第二遍出发前把该点深度清零，最终得到的最大深度就是直径长度。整体线性复杂度，适用于无边权或边权非负的树。
参考资料
思想
第一次 dfs 找到距离任意点最远的点 ，第二次 dfs 找到距离 最远的点 ，直径即为 。
实现
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
vector<int> G[N];
int dep[N],w=0;
void dfs(int u,int fa)
{
for(auto v:G[u])
{
if(v==fa)continue;
dep[v]=dep[u]+1;
if(dep[v]>dep[w])w=v;
dfs(v,u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
dep[w]=0;
dfs(w,0);
cout<<dep[w]<<'\n';
return 0;
}