Submission #44093838

---

Source Code Expand

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

using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;cin>>n;
  vector<vector<int>> T(n);
  for(int _=0;_<n-1;_++){
    int u,v;cin>>u>>v;u--;v--;
    T[u].push_back(v);
    T[v].push_back(u);
  }

  ll ans=n*(n-1)*(n-2)/6;

  vector<ll> sz(n,1);
  auto dfs=[&](auto dfs,int v,int pre)->void{
    ll sum1=0,sum2=0;
    for(int c:T[v]){
      if(c==pre)continue;
      dfs(dfs,c,v);
      sum1 += sz[c];
      sum2 += sz[c]*sz[c];
      sz[v]+=sz[c];
    }
    sum1 += n-sz[v];
    sum2 += (n-sz[v])*(n-sz[v]);
    ans -= (sum1*sum1 - sum2) >> 1;
  };
  dfs(dfs,0,-1);

  cout<<ans<<'\n';
}

Submission Info

Judge Result