树的直径

两个相隔最远的节点之间的路径
性质：1.如果有多条直径，那么这些直径一定拥有共同的中间部分
2.树上任意一点，相隔最远的点的集合，直径的两端点至少有一个在其中
求法：1.两次dfs
2.树形dp
具体代码请看

#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int he[maxn],ne[maxn<<1],to[maxn<<1],cnt;
int n;
void add(int x,int y)
{
	ne[++cnt]=he[x];
	to[cnt]=y;
	he[x]=cnt;
}
int dis[maxn],ans[maxn];
void dfs(int u,int f)
{
	if(f!=0)
	dis[u]+=dis[f]+1;
	for(int i=he[u];i;i=ne[i])
	{
		int v=to[i];
		if(v!=f)
		{
			dfs(v,u);
		}
	}
}
void solvedis()
{
	dfs(1,0);
	int start=1;
	for(int i=2;i<=n;i++)
	{
		if(dis[i]>dis[start])
		{
			start=i;
		}
	}
	dis[start]=0;
	memset(dis,0,sizeof(dis));
	dfs(start,0);
	int end=1;
	for(int i=2;i<=n;i++)
	{
		if(dis[i]>dis[end])
		end=i;
	}
	cout<<dis[end];
}
void dp(int u,int f)
{
	for(int i=he[u];i;i=ne[i])
	{
		int v=to[i];
		if(v!=f)
		{
			dp(v,u);
			ans[u]=max(ans[u],dis[v]+1+dis[u]);
			dis[u]=max(dis[u],dis[v]+1);
		}
	 } 
}
void solvedp()
{
	dp(1,0);
	int res=0;
	for(int i=1;i<=n;i++)
	{
		res=max(res,ans[i]);
	}
	cout<<res;
 } 
int main()
{
	
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
//	solvedis(); 
	solvedp();
	return 0;
}

练习错题
https://www.luogu.com.cn/problem/P2195
思路引导：这道题其实就是画图考虑可能性。要使直径最小，要么是两个树中最长的那个直径，要么是两者直径向上取整+1
https://www.luogu.com.cn/problem/P3629
https://www.luogu.com.cn/problem/P2491