P4185 [USACO18JAN] MooTube G (并查集 + 离线

#include
using namespace std;
using VI = vector<int>;
using ll = long long;
using PII = pair <int , int>;
const int mod = 998244353;
int f[200010];
int siz[200010];
 
 
int get_fa(int x){
    if(x != f[x]){
        f[x] = get_fa(f[x]);
    }
    return f[x];
}
 
void merge(int x, int y){
    x = get_fa(x);
    y = get_fa(y);
    if(x != y){
        f[x] = y;
        siz[y] += siz[x];
    }
}
 
int n,q;
struct edge{
    int x,y;
    int val;
    bool operator < (edge u){
        return val > u.val;
    }
 
}g[200050];
 
struct que{
    int k,v;
    int id;
    bool operator < (que u){
        return k > u.k;
    }
 
}h[200050];
VI res;
 
int main(){
    cin>>n>>q;
    res.resize(q);
    for(int i = 1 ; i <= n ; i++){
        f[i] = i;
        siz[i] = 1;
    }
    for(int i = 1 ; i <= n - 1 ; i++){
        cin>>g[i].x>>g[i].y>>g[i].val;
    }
    sort(g + 1 , g + 1 + n - 1);
    for(int i = 1 ; i <= q ; i++){
        cin>>h[i].k>>h[i].v;
        h[i].id = i;
    }
    sort(h + 1 , h + 1 + q);
   /* for(int i = 1 ; i <= n-1 ; i++) cout<
    cout<
    int j = 1;
    for(int i = 1 ; i <= q ; i++){
        while(j <= n - 1  && g[j].val >= h[i].k){
            merge(g[j].x , g[j].y);
            j++;
        }
        //cout<
        res[h[i].id] = siz[get_fa(h[i].v)] - 1;
 
    }
 
    for(int i = 1 ; i <= q ; i++){
        cout<"\n";
    }
}

跟我想法差不多，就是先离线下来，从大到小排列，

只有大于等于k的可以被推荐，所以每次将g[i].val  >= k 的加入并查集，保证所构成的树/森林中所有的边权都是大于等于k的