#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e5 + 5;
const int oo = 1e18, mod = 1e9 + 7;
int n, m, k, mid, uk, flag[N], marked[N];
vector<ii> adj[N];
vector<int> res;
int dfs(int x, int par) {
if (adj[x].size() == 1 && x != 0) return 0;
int mi = (1ll << 60), ma = -(1ll << 60);
for (auto tr : adj[x]) {
int y = tr.fi;
int d = tr.se;
if (y == par) continue;
int a = dfs(y, x);
if (a == 0 && flag[y] == 1) {
mi = min(mi, 0ll);
ma = max(ma, 0ll);
continue;
}
if (a < 0 && a + d <= 0) flag[x] = 1;
if (a < 0 && a + d > 0) a = 0;
else a += d;
if (a > mid) {
uk++;
marked[y] = 1;
a = min(-mid + d, 0ll);
if (-mid + d <= 0) flag[x] = 1;
flag[y] = 1;
}
ma = max(ma, a);
mi = min(mi, a);
}
if (-mi >= ma) {
return mi;
}
return ma;
}
int binary_search(int lo, int hi) {
while (lo < hi) {
mid = lo + (hi-lo)/2;
uk=0;
memset(flag, 0, sizeof(flag));
memset(marked, 0, sizeof(marked));
if (dfs(0,0)>0 || flag[0]==0) marked[0]=1, uk++;
if (uk<=k)
hi = mid;
else
lo = mid+1;
}
return lo;
}
void process() {
res.clear();
cin >> n >> k;
foru(i,1,n-1) {
int u, v, w; cin >> u >> v >> w;
u--, v--;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
mid=binary_search(0, oo);
uk=0;
cout << mid << '\n';
memset(flag, 0, sizeof(flag));
memset(marked, 0, sizeof(marked));
if (dfs(0,0)>0 || flag[0]==0) marked[0]=1, uk++;
foru(i,1,n) if (marked[i]==1) res.pb(i);
foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
for (auto x: res) cout << x << ' ';
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
process();
cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:
*/
Compilation message
Main.cpp: In function 'void process()':
Main.cpp:96:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
96 | foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
| ~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
395 ms |
34564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
345 ms |
37212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
