// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
long double rand_real(long double rmin, long double rmax) {
uniform_real_distribution<long double> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 2e5 + 20;
const long long inf = 1e18;
vector<pair<int, int>> adj[ms];
int deg[ms];
pair<int, int> par[ms];
long long mx[ms];
long long mi[ms];
bool f[ms];
long long res;
vector<int> cur;
vector<int> best;
int n, k;
void dfs(int u, int pr) {
for (auto x: adj[u]) {
int v = x.first;
int w = x.second;
if (v != pr) {
par[v] = {u, w};
dfs(v, u);
}
}
}
bool check(long long X) {
deque<int> q;
for (int i = 1; i <= n; i++) {
f[i] = true;
mx[i] = -inf;
mi[i] = inf;
deg[i] = adj[i].size();
if (i > 1 && deg[i] == 1) {
q.push_back(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop_front();
int v = par[u].first;
long long w = par[u].second;
if (mx[u] + w <= X && min(w, mi[u]) <= X) {
f[u] = false;
mx[v] = max(mx[v], max(0LL, mx[u]) + w);
mi[v] = min(mi[v], mi[u] + w);
}
else {
mi[v] = min(mi[v], w);
}
deg[v]--;
if (v > 1 && deg[v] == 1) {
q.push_back(v);
}
}
if (mi[1] <= X) {
f[1] = false;
}
cur.clear();
for (int i = 1; i <= n; i++) {
if (f[i]) {
cur.push_back(i);
}
}
return ((int)cur.size() <= k);
}
void just_do_it() {
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, -1);
long long lt = 0;
long long rt = 2e14;
while (lt <= rt) {
long long mt = (lt + rt) / 2;
if (check(mt)) {
best = cur;
res = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
for (int i = 1; i <= n; i++) {
f[i] = false;
}
for (auto x: best) {
f[x] = true;
}
for (int i = 1; i <= n; i++) {
if (!f[i] && (int)best.size() < k) {
best.push_back(i);
}
}
cout << res << '\n';
for (auto x: best) {
cout << x << " ";
}
}
// END MAIN CODE
Compilation message
Main.cpp: In function 'void file_io(std::string, std::string)':
Main.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen(fi.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen(fo.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
21156 KB |
Output is correct |
| 2 |
Correct |
226 ms |
21768 KB |
Output is correct |
| 3 |
Correct |
227 ms |
20024 KB |
Output is correct |
| 4 |
Incorrect |
453 ms |
18240 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
228 ms |
21756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
