题解 [USACO18JAN] MooTube G

题目链接

可以发现，对于一个固定的 \(k\)，所有边权小于 \(k\) 的边对答案是没有贡献的，因为一条边的相关性是最小相关性，这也意味着我们不能从 \(<k\) 的边到达其他的点。

由于本题有多组询问，所以对于没有用的边，将其看做被删除，有用的边，将其看做被插入。

考虑到本题实际上要维护连通块的大小，所以想到用并查集维护。

对于所有问题，不妨按 \(k\) 从大到小排序，然后依次插入符合 \(k\) 条件的边，这样就将删除操作去掉了。

时间复杂度 \(O(n\log n)\) ，瓶颈在排序。

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

#define PII pair<int,int>
typedef long long LL;
typedef unsigned long long ULL;

LL read() {
    LL sum=0,flag=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=1e5+10;
int n,q;
int ans[N];
int fa[N],siz[N];
struct node {
    int p,q,r;
}a[N];
struct node2 {
    int k,v,id;
}b[N];

int cmp1(node x,node y) {
    return x.r>y.r;
}

int cmp2(node2 x,node2 y) {
    return x.k>y.k;
}

int find(int x) {
    if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}

int main() {
    cin>>n>>q;
    for(int i=1;i<n;i++) {
        cin>>a[i].p>>a[i].q>>a[i].r;
    }
    for(int i=1;i<=n;i++) {
        siz[i]=1;
        fa[i]=i;
    }
    sort(a+1,a+n,cmp1);
    for(int i=1;i<=q;i++) {
        cin>>b[i].k>>b[i].v;
        b[i].id=i;
    }
    sort(b+1,b+1+q,cmp2);
    int num=0;
    for(int i=1;i<=q;i++) {
        while(a[num+1].r>=b[i].k&&num+1<=n-1) {
            num++;
            int fx=find(a[num].p),fy=find(a[num].q);
            if(fx!=fy) {
                fa[fx]=fy;
                siz[fy]+=siz[fx];
                siz[fx]=0;
            }
        }
        ans[b[i].id]=siz[find(b[i].v)]-1;
    }
    for(int i=1;i<=q;i++) {
        cout<<ans[i]<<'\n';
    }


    return 0;
}
/*

*/