Introduction to ACM [tree diameter]

The diameter of the tree : Is the longest chain in the tree .

There are generally two ways to find the diameter of a tree .

• Method 1 : Just find a spot ,dfs Find the farthest point , Then find the point dfs once , The furthest distance is the diameter .
• Method 2 : Just find a spot dfs once , Save the farthest way and secondary short circuit . shortest path + A short circuit +1 It's the diameter .

Take a look at the example :

https://ac.nowcoder.com/acm/contest/136/C
Method 1 :

#include<bits/stdc++.h>
using namespace std;
const int N=1e6*2+10;
int h[N],e[N],ne[N],idx,n;
int dist[N];
void add(int a,int b)
{
    
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa,int d)
{
    
	dist[u]=d;
	for(int i=h[u];i!=-1;i=ne[i])
	{
    
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u,d+1);
	}
}
int main(void)
{
    
	cin>>n;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++) 
	{
    
		int a,b; scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	dfs(1,-1,1);
	int root=1,len=0;
	for(int i=1;i<=n;i++) if(len<dist[i]) len=dist[i],root=i;// Find the farthest point 
	dfs(root,-1,1);// Run again .
	len=0;
	for(int i=1;i<=n;i++) len=max(len,dist[i]);// The furthest is the answer .
	cout<<len;
	return 0;
}

Method 2 :

#include<bits/stdc++.h>
using namespace std;
const int N=1e6*2+10;
int h[N],e[N],ne[N],idx,n;
int st[N],ans;
void add(int a,int b)
{
    
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
    
	int d1=0,d2=0;// The longest way , Second long road .
	st[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
    
		int j=e[i];
		if(st[j]) continue;
		int t=dfs(j);
		if(t>=d1) d2=d1,d1=t;
		else if(t>d2) d2=t;
	}
	ans=max(ans,d2+d1+1);
	return d1+1;
}
int main(void)
{
    
	cin>>n;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++) 
	{
    
		int a,b; cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}