Mootube (USACO Gold 2018 January)

答案是 $v[i]$ 所以在边大于等于 $k[i]$ 的component的大小。

这里的一个技巧是使用离线并查集的方法，就是按大到小加边，同时也按大到小执行查询。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
struct E {
    int p,q,r;
};
E es[100005];
bool rcmp(E &a, E &b) {return a.r > b.r;}
struct Q {
    int k,v,id;
};
Q qs[100005];       // k and v
bool kcmp(Q &a, Q &b) {return a.k > b.k;}
int fa[100005];
int cnt[100005];
int ans[100005];
 
int find(int x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
 
int main() {
    freopen("mootube.in", "r", stdin);
    freopen("mootube.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n-1; i++)
        scanf("%d %d %d", &es[i].p, &es[i].q, &es[i].r);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &qs[i].k, &qs[i].v);
        qs[i].id = i;
    }
    sort(es, es+n-1, rcmp);         // sort by decreasing r
    sort(qs, qs+m, kcmp);           // sort by decreasing k
 
    for (int i = 1; i <= n; i++)
        fa[i] = i, cnt[i] = 1;
    
    int j = 0;
    for (int i = 0; i < m; i++) {
        // query in decreasing k order
        int k = qs[i].k;
 
        // add edges with r >= k
        for (; j < n-1 && es[j].r >= k; j++) {
            E e = es[j];
            int pf = find(e.p), qf = find(e.q);
            fa[pf] = qf;
            cnt[qf] += cnt[pf];
        }
 
        // query result
        ans[qs[i].id] = cnt[find(qs[i].v)] - 1;
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
 
    return 0;
}