#include<bits/stdc++.h> using namespace std; #define int long long int n; vector<int>e[3005]; int fa[3005],sz[3005],son[3005],tp[3005],dep[3005]; void dfs(int p){ sz[p]=1; for(int x:e[p]){ if(x==fa[p])continue; fa[x]=p; dep[x]=dep[p]+1; dfs(x); sz[p]+=sz[x]; if(!son[p]||sz[x]>sz[son[p]])son[p]=x; } } void dfs1(int p,int top){ tp[p]=top; if(son[p])dfs1(son[p],top); for(int x:e[p]){ if(x==son[p]||x==fa[p])continue; dfs1(x,x); } } int lca(int x,int y){ while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]])swap(x,y); x=fa[tp[x]]; } return (dep[x]>dep[y]?y:x); } int getson(int x,int y){ while(tp[x]!=tp[y]){ if(fa[tp[y]]==x)return tp[y]; y=fa[tp[y]]; } return son[x]; } bool vis[100005]; int dp[3005][3005]; int dfs(int u,int v){ if(u>v)swap(u,v); if(dp[u][v])return dp[u][v]; if(u==fa[v])return dp[u][v]=sz[v]*(n-sz[v]); if(v==fa[u])return dp[u][v]=sz[u]*(n-sz[u]); int l=lca(u,v); if(l!=u&&l!=v){ dp[u][v]=max(dfs(fa[u],v),dfs(u,fa[v]))+sz[u]*sz[v]; } if(l==u){ int so=getson(u,v); // cout<<l<<" "<<u<<" "<<v<<" "<<so<<endl; dp[u][v]=max(dfs(so,v),dfs(u,fa[v]))+sz[v]*(n-sz[so]); } if(l==v){ int so=getson(v,u); dp[u][v]=max(dfs(fa[u],v),dfs(u,so))+sz[u]*(n-sz[so]); } return dp[u][v]; } void slv(){ int ans=0; // cout<<getson(1,7)<<endl; // cout<<dfs(7,9)<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)continue; ans=max(dfs(i,j),ans); // cout<<dp[i][j]<<" "; } // cout<<endl; } cout<<ans<<endl; } signed main(){ // freopen("luckyhowl.in","r",stdin); // freopen("luckyhowl.out","w",stdout); cin>>n; if(n==1){ cout<<0; return 0; } for(int i=1;i<n;i++){ int u,v; cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } dfs(1); dfs1(1,1); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }