每次给一个起点 然后询问和他相连的点的边权比k大的点有几个 路径边权是两点连接的所有路径上最小值
你需要一个可以合并的东西。
可并堆?
并查集就够了。
强制离线,每次把当前符合答案并上
答案就是当前联通块大小
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct edge{ int u,v,w; }e[N*4]; struct Que{ int v,k,id; }Q[N*2]; int fa[N]={}; int siz[N]={}; int ans[N]={}; int n,q; bool cmp1(edge A,edge B){ return A.w>B.w; } bool cmp2(Que A,Que B){ return A.id<B.id; } bool cmp3(Que A,Que B){ return A.k>B.k; } int getfa(int x){ if(x==fa[x])return x; else return fa[x]=getfa(fa[x]); } void merge(int x,int y){ // cout<<x<<" "<<y<<'\n'; int dx=getfa(x); int dy=getfa(y); fa[dx]=dy; siz[dy]+=siz[dx]; // cout<<dx<<" "<<dy<<'\n'; // getfa(dy) } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<n;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); } for(int i=1;i<=q;i++){ scanf("%d%d",&Q[i].k,&Q[i].v); Q[i].id=i; } sort(e+1,e+n,cmp1); sort(Q+1,Q+1+q,cmp3); int now=1; for(int i=1;i<=n;i++){ fa[i]=i; siz[i]=1; } for(int i=1;i<=q;i++){ while(now<=n-1&&e[now].w>=Q[i].k){ merge(e[now].u,e[now].v); now++; } ans[Q[i].id]=siz[getfa(Q[i].v)]; } for(int i=1;i<=q;i++){ cout<<ans[i]-1<<'\n'; } }