对于两个城市之间的过路费f(u, v)而言

f(u, v) = x 等价于 u 和 v 之间不能通过所有边权小于 x 的边连通。

所以此题思路如下:

将所有边权从小到大排序，一次加入每一条边，当加入的边权在(l,r)之间时，

如果这条边连接了两个不同的连通块，就统计出 f(u, v) = x 的点对数量。

即设这条边连接的两个连通块的大小分别为 sp 和 sq，则会产生 sp * sq 个满足条件的点对(乘法原理)

C++ 代码

#include<iostream>
#include<algorithm>
#include <cstring>
#define int long long

using namespace std;

const int N=100010, M = 400010;

int n,m,l,r;
int p[N],s[N];
int res;

struct edg{
    int u,v,w;
    bool operator < (const edg rhs){
        return this->w < rhs.w;
    }
}e[M];

int find(int x){
    if (p[x]!=x)  p[x]=find(p[x]);
    return p[x];
}

signed main(){
    cin>>n>>m>>l>>r;
    for(int i=1;i<=n;i++) p[i]=i,s[i]=1;   //s[i]维护的是连通块的大小
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+1+m); 
    int i=1;
    while(e[i].w<=r&&i<=m){   //这里注意下，最多把所有边遍历完就要终止循环了，不然很可能会出错
        int pa=find(e[i].u);
        int pb=find(e[i].v);
        if(pa!=pb){
            if(e[i].w>=l) res+=s[pa]*s[pb];  //乘法原理计算点对
            p[pa]=pb;                        //合并，并修改s[i]的值
            s[pb]+=s[pa];   
        }
        i++;
    }
    cout<<res;
    return 0;
}