(暴力遍历) $O(nlogn)$
由于要求最小值,所以可以联想到二分来解决答案(一般遇到求最大值或者最小值的题目,而题目中 N 的级别又达到了10^5 或者 10^6 的一般要用O(nlogn)来解决,我们一般首先想二分)
遍历树的时间复杂度是O(n), 加上二分就是O(nlogn),刚好可以过
从 0 ~ 1e7 + 10 开始二分,如果某条边的权重小于二分值,则该点及其子节点都不会访问到,所以可以直接不用管
最后统计根节点能够访问的节点数即可。
2022/10/3 补充:由于之前没有考虑双向边的问题,导致代码被hack掉了,这里把双向边加上,同时创建一个st状态数组,来表示每个点是否被遍历过就可以了
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e4 + 10, M = 2 * N;
int n, y;
int h[N], e[M], w[M], ne[M], idx = 0;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool check(int x)
{
memset(st, false, sizeof st);
int res = 1; // 根节点可以访问自己,所以 res 初始化为 1
queue<int> q;
q.push(0);
st[0] = true;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (w[i] >= x && !st[j]) q.push(j), st[j] = true, res ++; // 权重大于等于二分值 且 之前没有遍历过 我们才会继续往下遍历
}
}
return res <= y;
}
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
memset(h, -1, sizeof h);
idx = 0;
scanf("%d%d", &n, &y);
for (int i = 1; i <= n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 10000001;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
}
return 0;
}
互赞