求调 ABC F

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5+50;
int n,head[N],cnt,f[N],son[N],siz[N],top[N],depth[N],bel[N];
ll ans;
struct E{
  int next,to;
}e[N<<1];
inline void add(int x,int y){e[++cnt]=(E){head[x],y};head[x]=cnt;}
inline void dfs1(int now,int anc)
{
  siz[now]=1;
  if(f[now]==1)anc=now;
  bel[now]=anc;
  for(int i=head[now];i;i=e[i].next)
  {
    if(e[i].to==f[now])continue;
    f[e[i].to]=now;
    depth[e[i].to]=depth[now]+1;
    dfs1(e[i].to,anc);
    if(siz[e[i].to]>siz[son[now]])son[now]=e[i].to;
    siz[now]+=siz[e[i].to];
  }
}
inline void dfs2(int now,int tp)
{
  top[now]=tp;
  if(son[now])dfs2(son[now],tp);
  for(int i=head[now];i;i=e[i].next)
  {
    if(e[i].to==f[now]||e[i].to==son[now])continue;
    dfs2(e[i].to,e[i].to);
  }
}
inline int LCA(int x,int y)
{
  while(top[x]!=top[y])
  {
    if(depth[top[x]]<depth[top[y]])swap(x,y);
    x=f[top[x]];
  }
  if(depth[x]>depth[y])swap(x,y);
  return x;
}
inline bool check(int x,int y,int z)
{
  int a1=LCA(x,z),a2=LCA(y,z),lca=LCA(x,y);
  if((a1==z||a2==z)&&(LCA(z,lca)==lca))return true;
  return false;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<n;i++)
  {
    int u,v;cin>>u>>v;
    u++;v++;
    add(u,v);add(v,u);
  }
  dfs1(1,0);
  dfs2(1,1);
  int d1=1,d2=1,c1=n,c2=n;
  int cur=1;
  for(int i=head[1];i;i=e[i].next)
  {
    ans+=1ll*cur*siz[e[i].to];
    cur+=siz[e[i].to];
  }
  ans++;
  for(int i=2;i<=n;i++)
  {
    if(check(d1,d2,i))continue;
    if(check(d1,i,d2))
    {
      d2=i;
      c2=siz[i];
    }
    else if(check(d2,i,d1))
    {
      d1=i;
      c1=siz[i];
    }
    else break;
    if(d1==1)c1=n-siz[bel[d2]];
    if(d2==1)c2=n-siz[bel[d1]];
    ans+=1ll*c1*c2;
  }
  cout<<ans<<endl;
  return 0;
}