思路：这题的出题人是不是语文不行啊，题目意思说不清楚。
知道是求存在路径的点对数后，用并查集每次记录集合中点的数目，很容易就解决了。
#include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 200100 #define Maxm 800002 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 1000000000 #define lowbit(x) (x&(-x)) #define Mod 1000000007 using namespace std; int fa[Maxn],cnt; LL num[Maxn],ans[Maxn]; struct Edge{ int u,v,val; int operator< (const Edge &temp) const { return val<temp.val; } }p[Maxm]; struct Query{ int val,id; int operator< (const Query &temp) const{ return val<temp.val; } }q[Maxn]; void init() { for(int i=0;i<Maxn;i++){ fa[i]=i; ans[i]=0; num[i]=1; } } int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } LL merg(int a,int b) { int x=find(a); int y=find(b); if(x==y) return 0; LL ans=num[x]*num[y]; num[x]+=num[y]; fa[y]=x; ++cnt; return ans; } int main() { int n,m,t,i,j,u,v; while(scanf("%d%d%d",&n,&m,&t)!=EOF){ init(); for(i=1;i<=m;i++){ scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].val); } for(i=1;i<=t;i++) scanf("%d",&q[i].val),q[i].id=i; sort(p+1,p+1+m); sort(q+1,q+1+t); p[m+1].val=inf; p[m+1].u=1,p[m+1].v=1; j=1; LL sum=0; cnt=0; int pos=1; for(i=1;i<=m+1;i++){ while(j<=t&&q[j].val<p[i].val){ ans[q[j].id]=sum; j++; } sum+=merg(p[i].u,p[i].v); } while(j<=t&&q[j].val<p[i].val) { ans[q[j].id]=sum; j++; } for(i=1;i<=t;i++){ printf("%I64d ",ans[i]); } } return 0; }