一个很容易想到的思路是，枚举每一条边，算出各个点的入度 \(deg_i\)，同时用哈希表统计重边数量；然后，对于每个询问，枚举点对，求出 \(deg_x+deg_y-重边数量\)。这样做的复杂度是 \(O(m+qn^2)\)，怎么优化？
关注这个复杂度中的 \(n^2\)，它所做的事情可以抽象为：统计在 \(deg\) 数组中，有多少个数对的和大于 \(queries_i\)——不难发现，这可以通过排序+双指针解决。从大到小排序 \(deg\)，如果当前 \(deg_{left}+deg_{right}>queries_i\) 成立，那么左指针处在当前左指针（含）到右指针之间的所有位置时，这一条件都成立，答案增加 \(right-left\)，右指针左移 \(1\)；否则左指针右移 \(1\)。
去重方式也要随之改变：在完成双指针枚举后，我们枚举每一条边进行检查，如果 \(deg_x+deg_y>queries_i\)，但是 \(deg_x+deg_y-重边数量<queries_i\)，则答案减 \(1\)。
最终的时间复杂度是 \(O(m+q(n\log n+n+m))\)。
下面是 AC 代码：
func countPairs(n int, edges [][]int, queries []int) []int {
deg := make([]int, n+1)
type edge struct{ x, y int }
cntE := map[edge]int{}
for _, e := range edges {
x := e[0]
y := e[1]
if x > y {
x, y = y, x
}
deg[x]++
deg[y]++
cntE[(edge{x, y})]++
}
answer := make([]int, len(queries))
sortedDeg := append([]int(nil), deg...)
sort.Ints(sortedDeg)
for i, q := range queries {
left, right := 1, n
for left < right {
if sortedDeg[left]+sortedDeg[right] <= q {
left++
} else {
answer[i] += right - left
right--
}
}
for e, c := range cntE {
s := deg[e.x] + deg[e.y]
if s > q && s-c <= q {
answer[i]--
}
}
}
return answer
}