給你一個無向圖，無向圖由整數 n ，表示圖中節點的數目，和 edges 組成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之間有一條無向邊。同時給你一個代表查詢的整數數組 queries 。

第 j 個查詢的答案是滿足如下條件的點對 (a, b) 的數目：

a < b
cnt 是與 a 或者 b 相連的邊的數目，且 cnt 嚴格大于 queries[j] 。
請你返回一個數組 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 個查詢的答案。

請注意，圖中可能會有 多重邊 。

示例 1：

輸入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
輸出：[6,5]
解釋：每個點對中，與至少一個點相連的邊的數目如上圖所示。
answers[0] = 6。所有的點對(a, b)中邊數和都大于2，故有6個；
answers[1] = 5。所有的點對(a, b)中除了(3,4)邊數等于3，其它點對邊數和都大于3，故有5個。
示例 2：

輸入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
輸出：[10,10,9,8,6]

提示：

2 <= n <= 2 * 10${}^4$
1 <= edges.length <= 10${}^5$
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length

法一：我們可以先把每個點的度計算出來，然后對于一個查詢，它要求連接兩點之一的邊數大于一個值q，我們就可以把每個點的度排序，然后相向雙指針計算出兩點度之和大于q的點對數，但這樣計算可能會多算重復值，比如示例1中的邊12和邊21，這兩條邊計算出來點1和點2的度都是2，兩者相加就是4，但其實只有2條邊，我們需要用兩個點的度4減去相同的邊的數量2，如果減少2后的值小于等于q，則答案需要減去1對點對：

class Solution {
public:vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {// 保存每個點的度vector<int> deg(n + 1);// 保存兩點間的邊數unordered_map<int, int> cntEdge;for (vector<int> &edge : edges) {int x = edge[0];int y = edge[1];++deg[x];++deg[y];if (x > y) {swap(x, y);}// 可以用一個int保存兩個值小于等于65535的數// 這里表示從x到y的邊數增加1++cntEdge[x << 16 | y];}vector<int> sortedDeg = deg;sort(sortedDeg.begin(), sortedDeg.end());vector<int> ans(queries.size());for (int i = 0; i < queries.size(); ++i) {int left = 1;int right = n;while (left < right) {if (sortedDeg[left] + sortedDeg[right] > queries[i]) {ans[i] += right - left;--right;} else {++left;}}for (auto [k, c] : cntEdge) {int x = k >> 16;int y = k & 0xffff;// 如果點x和點y的度之和大于查詢目標值，說明該點對計入了答案// 如果減去相同的邊數后不大于查詢目標值了，說明該點對不應計入答案if (deg[x] + deg[y] > queries[i] && deg[x] + deg[y] - c <= queries[i]) {--ans[i];}}}return ans;}
};

如果edges的長度為m，queries的長度為q，則此算法時間復雜度為O(nlogn + q(n + m))，空間復雜度為O(n+m)，cntEdge的長度最多為m。

法二：我們可以構建一個數組，該數組的key為與點對相連的邊的數量，value為有多少個點對相連的邊的數量為key，這樣對于某個查詢q，答案就是數組下標大于q的所有元素和，即用后綴和來獲得答案：

class Solution {
public:vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {// 用時O(n)vector<int> deg(n + 1);unordered_map<int, int> cntEdge;// 用時O(m)for (vector<int> &edge : edges) {int x = edge[0];int y = edge[1];++deg[x];++deg[y];if (x > y) {swap(x, y);}++cntEdge[x << 16 | y];}// key為度，value為度為key的點數unordered_map<int, int> degToNum;// 用時O(n)for (int i = 1; i < deg.size(); ++i) {++degToNum[deg[i]];}int maxDeg = *max_element(deg.begin() + 1, deg.end());int k = maxDeg * 2 + 2;// key為與點對相連的邊的數量，value為點對相連的邊數為key的點對數量vector<int> degCnt(k);// 暴力計算任意兩點的度數和，并將度數和填入degCnt，計算后degCnt會包含重復邊// 如果邊的數量為m，這里的時間復雜度為m// 因為平均情況下假設有x種度數，則度數和為1+2+3+...+x=(1+x)x/2// 而度數和有2m個，因此x平均值為根號(4m)，兩重循環的平均時間就是O(m)for (auto [deg1, cnt1] : degToNum) {for (auto [deg2, cnt2] : degToNum) {// 為避免重復計算，只計算deg1<=deg2的情況// 如果是小于// 例如degToNum為[0,2,3]，表示度為1的有2個點，度為2的有3個點// deg1為1，deg2為2，此時度的和為5的點對數中，deg1和deg2貢獻了2*3個if (deg1 < deg2) {degCnt[deg1 + deg2] += cnt1 * cnt2;// 如果是等于// 例如度為3的點有4個，那么度的和為6的點對數中，deg1和deg2兩兩配對// 貢獻了cnt1 * (cnt1 - 1) / 2個} else if (deg1 == deg2) {degCnt[deg1 + deg2] += (cnt1 - 1) * cnt1 / 2;}}}// 去除重復邊，如果點對間有num個邊，說明該點對數實際與這兩點相連的邊數為s-num// 即度的和為s的兩點實際相連的邊數為s-num// 用時最大O(m)for (auto [edge, num] : cntEdge) {int s = deg[edge >> 16] + deg[edge & 0xffff];++degCnt[s - num];--degCnt[s];}// 計算后綴和// 用時O(m)，因為對于所有的點，每個點最多有m個度for (int i = k - 1; i > 0; --i) {degCnt[i - 1] += degCnt[i];}// 計算每個查詢的結果，查詢為q時，degCnt[q]為大于等于q的點對數// 在q只能取整數的情況下，degCnt[q+1]即為大于q的點對數// 超出索引時，查詢的答案為0// 此處我們用兩倍的最大度數加1表示超出索引// 上面雙重循環中，degCnt中最大key就是兩個最大度的和// 用時O(q)for (int &q : queries) {q = degCnt[min(q + 1, k - 1)];}return queries;}
};

此算法時間復雜度為O(n+m+q)，空間復雜度為O(n+m)。