Expert.
Put your skills to the test.

Problem summary

A connected undirected graph of N cities has exactly N−1 roads. Count unordered triples of distinct cities containing no road between any two chosen cities.

Constraints

1 ≤ N ≤ 100000; the roads form a tree.

Worked example

Official example, transcribed with whitespace restored from the PDF.

5
3 1
2 5
4 2
1 2

2

Solution analysis

1. There are C(N,3) triples before excluding adjacent cities. For every edge, exactly N−2 triples contain both its endpoints, giving (N−1)(N−2) edge incidences.
2. A triple containing two edges has been subtracted twice. Because the graph is a tree, its two edges share a middle vertex, and no triple can contain three edges. The number of such triples is the sum over vertices v of C(deg(v),2). Add this correction once.
3. The result is C(N,3)−(N−1)(N−2)+ΣC(deg(v),2). In the sample, this leaves exactly {1,4,5} and {3,4,5}. For fewer than three vertices the answer is zero.

Why it works

Every invalid triple has either one or two induced edges because a tree has no triangles. The formula subtracts a one-edge triple once; it subtracts a two-edge triple twice and adds it once through its unique middle vertex. Valid triples are never changed. Thus exactly the valid triples remain.

Watch out. Use 64-bit arithmetic for binomial products, even though each degree fits in int.

An independently written complete program with standard headers.

// Key idea: Every invalid triple has either one or two induced edges because a tree has no triangles.
// The formula subtracts a one-edge triple once; it subtracts a two-edge triple twice and adds it once
// through its unique middle vertex.
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin>>n;
    vector<long long>degree(n);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        ++degree[u-1];
        ++degree[v-1];
    }
    if(n<3){
        cout<<0<<'\n';
        return 0;
    }
    long long answer=n*(n-1)*(n-2)/6-(n-1)*(n-2);
    for(long long d:degree){
        answer+=d*(d-1)/2;
    }
    cout<<answer<<'\n';
}