AcWing 3712. 根能抵达的点
原题链接
简单
作者:
炽热的
,
2022-12-18 22:01:47
,
所有人可见
,
阅读 159
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int p[N], sz[N];
struct Edge {
int u, v, w;
bool operator< (const Edge& W) const {
return w < W.w;
}
}e[N];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1;
for (int i = 0; i < n - 1; i ++ ) {
auto &[u, v, w] = e[i];
cin >> u >> v >> w;
u ++ , v ++ ;
}
sort(e, e + n - 1);
int res = 0;
for (int i = n - 1; ~i; i -- ) {
auto [u, v, w] = e[i];
u = find(u), v = find(v);
if (u == v) continue;
sz[u] += sz[v];
p[v] = u;
if (sz[find(1)] > m) {
res = w + 1;
break;
}
}
cout << res << endl;
}
int main() {
int _; cin >> _;
while (_ -- ) solve();
return 0;
}