这道题目大家首先想到的应该是直接搜索，但是这道题目需要用并查集优化否则会 TLE 哦！
首先发现我们其实每个答案就是以 x 为起点，所有权都小于等于 w 的一个连通块中点的个数。
首先我们用并查集的基本思路为：
- 首先初始化每个点的父亲为它自己，每个集合的元素个数都初始化为 1 。
- 输入。
- 先暂且隐藏：一个神秘优化。
- 遍历 x ，如果有联通的并且权小于等于 w 则就将这两个集合合并。
- 最后输出答案。
我们先给出每个部分的伪代码：
- 首先初始化每个点的父亲为它自己，每个集合的元素个数都初始化为 1 。
for(int i=1;i<=n;i++)f[i]=i,cnt[i]=1;
- 输入
for(int i=1;i<=m;i++)cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=q;i++){
cin>>b[i].x>>b[i].w;
b[i].i=i;//记录每个起点的 id
}
- 遍历 x ，如果有联通的并且权小于等于 w 则就将这两个集合合并。
for(int i=1;i<=q;i++){
int w=b[i].w;
while(/*满足条件*/){
l++;
join(a[l].u,a[l].v);//合并函数
}
ans[b[i].i]=cnt[find(b[i].x)];//记录答案
}
- 输出
for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
那么我们之前提到的神秘优化是什么呢？就是优化遍历顺序
我们注意到当英雄攻击力越小连通块的点的个数也就越少，为了不重复计算，我们可以从最小的开始遍历到最大的。
也就是我们要通过攻击力将每个单独的问题排序。
同样的我们也需要将每个路径按照边权的大小升序排序，这样就可以 AC此题啦。