/** 给定一棵树，要求给树边赋值[0,n-2]，每个值只能使用一次 S = mex(u,v), mex(u,v)是u-v路径上没有出现过的编号最小的值 问使得S最大的赋值方式 由于很难直接统计答案，所以考虑统计每条边的贡献 包含(0)路径的贡献tot1是其左右子树size的乘积 包含(0,1)的路径的贡献tot2是其左右子树的size乘积 ...依次类推 显然：只包含(1,2)这样的路径是没有贡献的 那么原问题转化为如何分配[0,n-2],使得最后的乘积和最大 dp[u][v]表示路径(u,v)的贡献 ，O(n^2)的时间内求完即可 显然root不同，答案也会不同，所以先预处理出 size[root][u],表示以root为根时u的儿子大小 fa[root][u],表示以root为根时u的父亲 两重循环+记忆化搜索求出所有dp[u][v] */ #include<bits/stdc++.h> using namespace std; #define N 3005 #define ll long long vector<int>G[N]; ll n,dp[N][N],size[N][N],fa[N][N]; void dfs(int u,int pre,int root){ size[root][u]=1;fa[root][u]=pre; for(auto v:G[u]){ if(v==pre)continue; dfs(v,u,root); size[root][u]+=size[root][v]; } } ll solve(int u,int v){ if(u==v)return 0; if(dp[u][v]!=-1)return dp[u][v]; dp[u][v]=size[u][v]*size[v][u] +max(solve(u,fa[u][v]),solve(v,fa[v][u])); return dp[u][v]; } int main(){ cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } for(int root=1;root<=n;root++) dfs(root,0,root); memset(dp,-1,sizeof dp); ll ans=0; for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) ans=max(ans,solve(u,v)); cout<<ans<<' '; }