树的直径

树的直径就是树上两点的最远距离。

如果暴力 dfs 会发现，最后情况下每一次都把树跑满，时间复杂度 $O(n^2)$，显然是不可以通过 $10^5$ 的数据的。 考虑优化成 $O(n)$。

假设有一点 $x$，通过一次 $O(n)$ 的 dfs 找到了自己的最远的是 $y$，此时发现，如果再跑一次以 $y$ 为起点的 dfs，这个 dfs 中的跑的距离就是答案了。

注意点 1.实现时 dfs 中的边界。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int n;
bool vis[N];
int ans;
int sum;
int a,b;
void dfs(int u,int cnt){
	if(cnt>sum){
		sum=cnt;
		ans=u;
	}
	vis[u]=1;
	for(auto ne:g[u]){
		if(!vis[ne]){
			dfs(ne,cnt+1);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	a=ans;
	sum=ans=0;
	memset(vis,0,sizeof vis);
	dfs(a,0);
	cout<<sum;
	return 0;
}