树的直径即为一棵树上的最长链。一般分为有负权图和无负权图来考虑。
无负权
只需做两次dfs。
第一次是搜索出从任一点出发到达的最远的点P，那么这个点就一定在最长链上（请自证）。
第二次搜索从点P出发到达的最远的点Q，那么最长链即为P与Q的距离。
题目：B4016 树的直径
代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, lth[N], ans, mx, pas;
vector <int> e[N];
void dfs(int u, int fa)
{
lth[u] = lth[fa] + 1;
if(lth[u] > mx) mx = lth[u], pas = u;
for(int i = 0; i < e[u].size(); i ++)
{
if(e[u][i] == fa) continue;
dfs(e[u][i], u);
}
}
int main()
{
cin >> n;
int u, v;
for(int i = 1; i < n; i ++)
{
scanf("%d %d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 0);
mx = 0;
memset(lth, 0, sizeof(lth));
dfs(pas, 0);
ans = mx;
cout << ans - 1 << endl;
return 0;
}