LC高分段+周赛4题专题训练

统计点对的数目

该题目简化为：

• 对于每一个query：
  • 先统计所有满足q的点对
  • 去重

（其实也是考虑如何去重的过程，即动态计算组合数的过程）

知识点：双指针

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
        deg = [0] * (n+1)
        for a, b in edges:
            deg[a] += 1
            deg[b] += 1
        s_deg = sorted(deg)
        c_e = Counter(tuple(sorted(i)) for i in edges)
        ans = []
        for q in queries:
            now = 0
            l, r = 1, n
            while l < r:
                if s_deg[l] + s_deg[r] > q:
                    now += r - l
                    r -= 1
                else:
                    l += 1
            for (a,b), c in c_e.items():
                if deg[a] + deg[b] - c <= q \
                and deg[a] + deg[b] > q:
                    now -= 1
            ans.append(now)
        return ans