We want to count pairs (x,y) such that degree[x] + degree[y] - occurrences(x,y) > k
提示 2
Think about iterating on x, and counting the number of valid y to pair with x.
提示 3
You can consider at first that the (- occurrences(x,y)) isn't there, or it is 0 at first for all y. Count the valid y this way.
提示 4
Then you can iterate on the neighbors of x, let that neighbor be y, and update occurrences(x,y).
提示 5
When you update occurrences(x,y), the left-hand side decreases. Once it reaches k, then y is not valid for x anymore, so you should decrease the answer by 1.
