我使用了两次 dfs 求解直径，随后枚举了直径上的所有点 dfs 求最远点。感觉是 $O(n^2)$ 的，但直接过了。(附记录R161950652)

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n,t,p,ans1,ans2;
int h[N],cnt,l1,l2,l3;
int dep[N],fa[N],pth[N];
bool ond[N];

struct Edge{
	int u,v;
}e[N<<1];

void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].u=h[u];
	h[u]=cnt;
}

int dfs(int u,int f){
	int nd=u;
	fa[u]=f;
	dep[u]=dep[f]+1;
	for(int i=h[u],v,l;i;i=e[i].u){
		v=e[i].v;
		if(v==f||ond[v])continue;
		l=dfs(v,u);
		if(dep[l]>dep[nd])nd=l;
	}
	return nd;
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	l1=dfs(1,0);
	l2=dfs(l1,0);
	ans1=dep[l2]-1;
	ond[l1]=ond[l2]=1;
	
	int d=p=fa[l2];
	pth[++t]=l2;
	while(!ond[d]){
		ond[d]=1;
		pth[++t]=d;
		d=fa[d];
	}
	pth[++t]=l1;
	//在这里枚举
	for(int i=1,x;i<=t;i++){
		x=dfs(pth[i],0);
		if(dep[x]>ans2){
			ans2=dep[x];
			l3=x;
		}
	}
	if(ond[l3])l3=p;
	cout<<(ans1+ans2-1)<<endl;
	cout<<l1<<' '<<l2<<' '<<l3;
	return 0;
}

如果确实是 $O(n^2)$ 的，能否给出卡掉本代码的树的构造?

如果是 $O(n \log n)$ 或更低的复杂度，能否给出证明?