思路：

推出斜率优化公式后，会发现最优点只可能来自凸斜率中的第一个元素和最后一个元素，

这两个元素不用维护凸斜率也能知道，就是第一个和上一个元素

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb emplace_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pli pair
       
        #define pii pair
        
         #define piii pair
         
          #define pdd pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//head const int N = 5e5 + 5;vector
           
             g[N];int n, u, v, sz[N];LL dp[N], ans;//(dp[j]-dp[k]+sz[j]^2-sz[k]^2)/(sz[j]-sz[k]) >= 2*(n-sz[i]) k < jbool _g(int k, int j, LL C) { return (dp[j]-dp[k]+sz[j]*1LL*sz[j]-sz[k]*1LL*sz[k]) <= C*(sz[j]-sz[k]);}//(dp[i]-dp[j]+sz[i]^2-sz[j]^2)/(sz[i]-sz[j]) >= (dp[j]-dp[k]+sz[j]^2-sz[k]^2)/(sz[j]-sz[k])//k < j < ibool gg(int k, int j, int i) { return (dp[i]-dp[j]+sz[i]*1LL*sz[i]-sz[j]*1LL*sz[j])*(sz[j]-sz[k]) <= (dp[j]-dp[k]+sz[j]*1LL*sz[j]-sz[k]*1LL*sz[k])*(sz[i]-sz[j]);}void dfs(int u, int o) { sz[u] = 1; for (int v : g[u]) { if(v != o) { dfs(v, u); ans = min(ans, (n-sz[v])*1LL*(n-sz[v]) + sz[v]*1LL*sz[v]); sz[u] += sz[v]; } } dp[u] = sz[u]*1LL*sz[u]; for (int v : g[u]) { if(v != o) { dp[u] = min(dp[u], (sz[u]-sz[v])*1LL*(sz[u]-sz[v])+dp[v]); } } sort(g[u].begin(), g[u].end(), [](int x, int y){ return sz[x] > sz[y]; }); int l = -1, r = -1; for (int v : g[u]) { if(v == o) continue; if(l == -1) { l = r = v; continue; } int x = l; ans = min(ans, dp[v]+dp[x]+(n-sz[v]-sz[x])*1LL*(n-sz[v]-sz[x])); x = r; ans = min(ans, dp[v]+dp[x]+(n-sz[v]-sz[x])*1LL*(n-sz[v]-sz[x])); r = v; }}int main() { scanf("%d", &n); for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u); int rt = 1; for (int i = 1; i <= n; ++i) if(g[i].size() != 1) rt = i; ans = n*1LL*n; dfs(rt, rt); printf("%lld\n", n*1LL*(n-1) - (ans-n)/2); return 0;}