MooTube G

采用并查集解决问题，分成两个集合查询和视频相关度，然后将二者按降序排序，从高到低处理，逐步合并满足条件的边，用并查集维护连通集合大小，根据k的从大到小，避免了重复对并查集的构建，如果k变小，就直接把符合条件的新的视频加进来，最后直接得到查询结果。

#include<bits/stdc++.h>
using namespace std;

struct E {
    int x, y, z;
};

E f[100005];
struct Query {
    int k, v, idx; 
} q[100005];

int n, Q;
int a[100005]; 
int sz[100005];
int ans[100005]; 
int e_ptr; 
bool cmp(E a, E b) {
    return a.z > b.z;
}
bool cmp_q(Query a, Query b) {
    return a.k > b.k;
}
int gf(int x) {
    if (a[x] == x) return x;
    return a[x] = gf(a[x]);
}
void ad(int x, int y) {
    x = gf(x);
    y = gf(y);
    if (x != y) {
        a[x] = y;
        sz[y] += sz[x];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> Q;
    // 并查集初始化
    for (int i = 1; i <= n; i++) {
        a[i] = i;
        sz[i] = 1;
    }
    // 读入视频连接边
    for (int i = 1; i <= n-1; i++) {
        cin >> f[i].x >> f[i].y >> f[i].z;
    }
    // 读入查询
    for (int i = 1; i <= Q; i++) {
        cin >> q[i].k >> q[i].v;
        q[i].idx = i;
    }
    // 排序边和查询
    sort(f + 1, f + n, cmp);
    sort(q + 1, q + Q + 1, cmp_q);

    e_ptr = 1;
    // 处理每个查询
    for (int i = 1; i <= Q; i++) {
        int k = q[i].k, v = q[i].v;
        // 合并所有相关值≥k的边
        while (e_ptr <= n-1 && f[e_ptr].z >= k) {
            ad(f[e_ptr].x, f[e_ptr].y);
            e_ptr++;
        }
        // 记录
        ans[q[i].idx] = sz[gf(v)] - 1;
    }
    // 输出答案
    for (int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}