Submission #44073550

---

Source Code Expand

//Somos insignificantes. Por mais que você programe sua vida, a qualquer momento tudo pode mudar.
// If you have God on your side,everything becomes clear
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//To convert it into pairs use pair<int,int> instead of int and also make less_equal<pair<int,int>> 

template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// To use ordered use ordered_multiset<type>S something like this

// n >>(k+1) << (k) + n%(1<<k+1)-1<<k;

#define ar array
#define ll long long
#define ld long double
#define sza(x) ((ll)x.size())
#define all(a) (a).begin(), (a).end()

const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
#define endl '\n';
#define fi first
#define popcount(x) __builtin_popcountll(x)
#define se second
#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)
 /*vector<int> primes, is_prime, spf;

 void sieve(int n) {
     primes.clear();
     is_prime.assign(n + 1, 1);
     spf.assign(n + 1, 0);
     is_prime[0] = is_prime[1] = false;
     for(ll i=2;i<=n;i+=2){
         spf[i]=2;
         if(i!=2)is_prime[i]=false;
     }
     for (ll i = 3; i*i <= n; i++) {
         if (is_prime[i]) {
             primes.push_back(i);
             spf[i] = i;
             for (ll j = i * i; j <= n; j += i) {
                 is_prime[j] = false;
                 spf[j] = i;
             }
         }
     }
 }
*/

/* struct cmp{
    bool operator()(const pair<int,int>& v1,const pair<int,int>& v2) const{
    	
    }};*/
 long long binpow(long long a, long long b) {
    a %=MOD;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    res=res%MOD;
    return res;
}
ll n;
vector<vector<ll>>g;
vector<ll>sz;
ll ans=0;
void dfs(ll u,ll p){
    sz[u]=1;
    for(auto & x:g[u]){
        if(x==p)continue;
        dfs(x,u);
        sz[u]+=sz[x];
    }
}
void dfs2(ll u,ll p){
    ll rem = n-sz[u];
    ans+=rem*(sz[u]-1);
    ll pp=0;
    for(auto & x:g[u]){
        if(x==p)continue;
        pp+=sz[x];
    }
    for(auto & x:g[u]){
        if(x==p)continue;
        pp-=sz[x];
        ans+=sz[x]*pp;
        dfs2(x,u);
    }
}


void solve() {
    cin>>n;
    g.resize(n+1);
    sz.resize(n+1);
    for(ll i=0;i<n-1;i++){
        ll a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    dfs2(1,0);
    ans=((n*(n-1)*(n-2))/6) - ans;
    cout<<ans;
  


}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    
    int tc=1;// cin >> tc;
    for (int t = 1; t <= tc; t++) {
        //cout << "Case #" << t  << ": ";
        solve();
    }
}

Submission Info

Judge Result