1 条题解
-
-1GCOJ Official (Cui2010) LV 8 MOD @ 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