题意:给你n个点,m条边构成无向图。q个询问,每次一个值,求有多少条路,路中的边权都小于这个值
a->b 和 b->a算两种
思路:把权值从小到大排序,询问从小到大排序,如果相连则用并查集相连形成联通块
x个点可以形成:x * (x - 1)
如果新增的路使两个联通块和并则数量 增长了:
(num[1]+num[2])×(num[1]+num[2]-1) - num[1] × (num[1]-1) - num[2] ×(num[2]-1)
#include#include #include #include #include #include #include #include