#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("trapv")
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <pair <int, ll>> adj2[MAXN];
vector <pair <int, ll>> adj[MAXN];
ll mid;
int n, k;
bool vis[MAXN];
int cnt = 0;
vector <int> u, ans_vec;
void add (int pos) {
//cout << "LOL: " << pos << '\n';
u.push_back(pos);
}
pair <ll, ll> dfs (int pos, int par = -1) {
vis[pos] = 1;
if (par != -1 && adj[pos].size() == 1) return {0, 0};
if (par == -1 && adj[pos].empty()) {
cnt++; add(pos); return {0, 0};
}
vector <pair <ll, ll>> good, bad;
int flag = 0;
for (auto j : adj[pos]) {
if (j.first == par) continue;
auto k = dfs(j.first, pos);
if (k.second == 0) {
if (k.first + j.second > mid) {
flag++; add(j.first); good.push_back({j.second, 1});
} else bad.push_back({k.first + j.second, 0});
} else {
if (k.first + j.second > mid) continue;
good.push_back({k.first + j.second, 1});
}
}
cnt += flag;
sort(good.begin(), good.end());
sort(bad.begin(), bad.end());
/*
cout << pos << " : \n";
for (auto j : good) cout << j.first << " " << j.second << " | ";
cout << '\n';
for (auto j : bad) cout << j.first << " " << j.second << " | ";
cout << '\n' << '\n';
*/
if (par == -1 && good.empty() && bad.empty()) {
cnt++; add(pos); return {0, 1};
}
if (good.empty() && bad.empty()) {
return {0, 0};
}
if (par == -1) {
if (bad.empty()) return {0, 0};
if (good.empty()) {
cnt++; add(pos); return {0, 0};
}
if (bad.back().first + good.front().first > mid) {
cnt++; add(pos); return bad.back();
}
return good.front();
}
if (bad.empty()) {
return good.front();
}
if (good.empty()) return bad.back();
if (bad.back().first + good.front().first > mid) return bad.back();
return good.front();
}
bool check () {
cnt = 0; u.clear();
for (int i = 1; i <= n; i++) {
vis[i] = 0; adj[i].clear();
for (auto j : adj2[i]) {
if (j.second <= mid) {
adj[i].push_back(j);
}
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
//cout << i << " L L L L " << cnt << '\n';
}
}
//cout << mid << " " << cnt << '\n';
return cnt <= k;
}
int main () {
cin >> n >> k;
for (int i = 1; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
adj2[a].push_back({b, c});
adj2[b].push_back({a, c});
}
//mid = 47; cout << check() << '\n'; return 0;
ll l = 0, r = 1e16; ll ans = 1;
while (l <= r) {
mid = (l + r) >> 1;
if (check()) {
ans_vec = u;
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
cout << ans << '\n'; return 0;
set <int> pp; for (int i = 1; i <= n; i++) pp.insert(i);
for (auto i : ans_vec) {
cout << i << " "; pp.erase(i); k--;
}
while (k--) {
cout << *(--pp.end()) << " "; pp.erase(pp.end());
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1316 ms |
68944 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1514 ms |
71380 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
