洛谷P4185 离线+并查集

好题，发现没有强制在线，可以离线操作

排序之后带集合点数的并查集就好了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
int p[N],sz[N];int find(int x){if(x!=p[x])p[x] = find(p[x]);return p[x];
}
struct Node{int k,v,id;bool operator<(const Node&W)const{return k>W.k;}
}query[N];
struct Edge{int p,q,r;bool operator<(const Edge&Ws)const{return r>Ws.r;}
}edge[N];
vector<int>ans(100020,0);
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)p[i] = i,sz[i] = 1;for(int i=1;i<=n-1;i++){int p,q,r;cin>>p>>q>>r;edge[i] = {p,q,r};}for(int i=1;i<=m;i++){int k,v;cin>>k>>v;query[i] = {k,v,i};}sort(edge+1,edge+1+n-1);sort(query+1,query+1+m);for(int i=1,j=0;i<=m;i++){int ks = query[i].k;while(j+1<=n&&edge[j+1].r>=ks){++j;int a = find(edge[j].p),b = find(edge[j].q);if(a!=b){sz[b]+=sz[a];p[a] = b;}}ans[query[i].id] = sz[find(query[i].v)]-1;}for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}