CF142 Div1 C - Triangles

問題

n頂点の完全無向グラフがあり、そこからアリスはm本の辺を取り、残りの辺はボブに渡した
二人が持っているグラフそれぞれにおける長さ3の閉路(=triangleと呼ぶ)の個数の和を求めよ

1 <= n <= 10^6
0 <= m <= 10^6

解法

各頂点を1個ずつ見ていき、その頂点に繋がっているn-1本の辺から2本選んでできるペア全てについて
両方の辺がアリスかボブのグラフに含まれる場合) +2をスコアに足す
片方はアリス、他方はボブのグラフに含まれる場合) -1をスコアに足す
としていく
するとアリスorボブのグラフでtriangleになっている部分はスコア6点分にあたり、triangleになっていない部分は0点にあたる
だからこのスコアを最後に6で割ったものが答えになる

アリスのグラフで頂点vに直接繋がっている辺の本数をdとすると、ボブのグラフでのそれは当然n-d-1本になり、スコアの増分は
2(dC2) - d(n-d-1) + 2((n-d-1)C2)
となるから合計スコアはO(n)で計算できる

この解法天才すぎない？数オリかよ

ll n, m, a, b, e[1001001], ans;

signed main() {
	cin >> n >> m;
	rep(i,m) {
		cin >> a >> b;
		a--, b--;
		e[a]++, e[b]++;
	}
	rep(i,n) {
		ll d = e[i];
		ans += d*(d-1) - d*(n-d-1) + (n-d-1)*(n-d-2);
	}
	cout << ans/6 << endl;
}