1 条题解

  • -1
    @ 2021-10-22 20:27:07

    我们将所有的 \(k\) 按 从大到小 排序,边也是的。

    然后对于每次查询,将满足条件的边扔到一个并查集里。

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    vector<pair<pair<int, int>, int> > ge;
    int fa[100001], sz[100001];
    int FindFather(int n){
        if(fa[n] == n){
            return n;
        }
        return fa[n] = FindFather(fa[n]);
    }
    void Union(int u, int v){
        sz[FindFather(v)] += sz[FindFather(u)];
        sz[FindFather(u)] = sz[FindFather(v)];
        fa[FindFather(u)] = FindFather(v);
    }
    void add_edge(int a, int b, int c){
        ge.push_back(make_pair(make_pair(a, b), c));
    }
    bool cmp(pair<int, pair<int, pair<int, int> > > a, pair<int, pair<int, pair<int, int> > > b){
        return a.second.second.first > b.second.second.first;
    }
    bool cmp1(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
        return a.second > b.second;
    }
    signed main(){
        int n, q;
        cin >> n >> q;
        for(int i = 0;i < n - 1;i++){
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w);
        }
        pair<int, pair<int, pair<int, int> > > p[q];
        for(int i = 0;i < q;i++){
            cin >> p[i].second.second.first >> p[i].second.second.second;
            p[i].second.first = 0, p[i].first = i;
        }
        sort(p, p + q, cmp);
        sort(ge.begin(), ge.end(), cmp1);
        for(int i = 1;i <= n;i++){
            fa[i] = i, sz[i] = 1;
        }
        int t = 0;
        for(int i = 0;i < q;i++){
            while(t < ge.size() && ge[t].second >= p[i].second.second.first){
                Union(ge[t].first.first, ge[t].first.second);
                t++;
            }
            p[i].second.first = sz[FindFather(p[i].second.second.second)] - 1;
        }
        sort(p, p + q);
        for(int i = 0;i < q;i++){
            cout << p[i].second.first << endl;
        }
        return 0;
    }
    
  • 1

信息

ID
1019
难度
9
分类
数据结构 | 并查集 点击显示
标签
递交数
5
已通过
3
通过率
60%
被复制
1
上传者